2013 ACMICPC 항주 라이브 I 문제
8111 단어 ICPC
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define Maxn 100
using namespace std;
int dp[1<<21],num[Maxn],bag[Maxn][Maxn],g,b,s,now[22];
bool vi[Maxn];
int dfs(int S,int now[])
{
if(vi[S]) return dp[S];
if(S==0) return 0;
int a[22],c[22];
int i,j,f;
int ans=-10000000;
int num=0;
vi[S]=1;
memcpy(c,now,sizeof(c));
for(i=0;i<b;i++){
if((1<<i)&S){
for(j=1;j<=g;j++){
c[j]+=bag[i+1][j];
}
}
}
for(j=1;j<=g;j++)
num+=c[j]/s;
for(i=0;i<b;i++){
if((1<<i)&S){
f=0;
memcpy(a,now,sizeof(a));
for(j=1;j<=g;j++){
a[j]+=bag[i+1][j];
f+=a[j]/s;
a[j]%=s;
}
if(f)
ans=max(ans,f+dfs(S^(1<<i),a));
else
ans=max(ans,num-dfs(S^(1<<i),a));
}
}
return dp[S]=ans;
}
void solve()
{
int i,j,N;
N=(1<<b)-1;
dp[0]=0;
dfs(N,now);
int sum=0,cnt[22];
memset(cnt,0,sizeof(cnt));
for(i=1;i<=b;i++){
for(j=1;j<=g;j++){
cnt[j]+=bag[i][j];
}
}
for(i=1;i<=g;i++)
sum+=cnt[i]/s;
printf("%d
",2*dp[N]-sum);
}
int main()
{
int i,j;
while(scanf("%d%d%d",&g,&b,&s)!=EOF,g||b||s){
memset(bag,0,sizeof(bag));
memset(num,0,sizeof(num));
memset(dp,-63,sizeof(dp));
memset(vi,0,sizeof(vi));
memset(now,0,sizeof(now));
int x;
for(i=1;i<=b;i++){
scanf("%d",&num[i]);
for(j=1;j<=num[i];j++){
scanf("%d",&x);
bag[i][x]++;
}
}
solve();
}
return 0;
}
사고방식: 기억화 검색.
dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2013 ACMICPC 항주 라이브 I 문제사고방식: 기억화 검색. dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.