極度郁悶地完成了這一題……倒不是因為名字是“情敵”，而是我的測評系統(tǒng)似乎出了問題，導致我一直60分。后來把文件復制一份，新建文件夾，重新測評，100！當時快氣爆了！
此題的方法是搜索+DP
如果忽略“超級情敵”不管，發(fā)現(xiàn)這是個二維費用的背包。超級情敵最多有4個，有三種情況：不消滅，第1月消滅，第2月消滅，先搜索這些情況，再DP。
以下是我的代碼。
#include<stdio.h>
#define maxn 51
#define maxab 101
typedef unsigned __int64 int64;
FILE *fin,*fout;
int a,b,n,m,p[maxn]=
{0},num[5],flag[5],super[maxn]={0};
long w[maxn],t[maxn];
int64 d[maxn][maxab][maxab],ans,sum;
void init()
{
int i,j,x,tot;
sum=0;
ans=0;
fin=fopen("rival.in","r");
fscanf(fin,"%d%d",&a,&b);
fscanf(fin,"%d%d",&n,&m);
for(i=1;i<=n;i++)
{
fscanf(fin,"%ld%ld",&w[i],&t[i]);
sum+=w[i];
}
for(i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&num[i],&tot);
super[num[i]]=1;
for(j=1;j<=tot;j++)
{
fscanf(fin,"%d",&x);
p[x]=i;
}
}
fclose(fin);
}
void dp(int t1,int t2,int64 now)
{
int i,j,k;
int64 last=0;
for(i=1;i<=n;i++)
for(j=0;j<=t1;j++)
for(k=0;k<=t2;k++)
d[i][j][k]=0;
for(i=1;i<=n;i++)
for(j=0;j<=t1;j++)
for(k=0;k<=t2;k++)
{
d[i][j][k]=d[i-1][j][k];
if(!super[i])
{
if((p[i]==0||flag[p[i]]<=1)&&j>=t[i]&&d[i-1][j-t[i]][k]+w[i]>d[i][j][k])
d[i][j][k]=d[i-1][j-t[i]][k]+w[i];
if((p[i]==0||flag[p[i]]<=2)&&k>=2*t[i]&&d[i-1][j][k-2*t[i]]+w[i]>d[i][j][k])
d[i][j][k]=d[i-1][j][k-2*t[i]]+w[i];
}
if(d[i][j][k]>last) last=d[i][j][k];
}
if(now+last>ans) ans=now+last;
}
void dfs(int dep,int t1,int t2,int64 now)
{
if(dep>m)
{
dp(t1,t2,now);
return;
}
if(t1>=t[num[dep]])
{
flag[dep]=1;
dfs(dep+1,t1-t[num[dep]],t2,now+w[num[dep]]);
}
if(t2>=2*t[num[dep]])
{
flag[dep]=2;
dfs(dep+1,t1,t2-2*t[num[dep]],now+w[num[dep]]);
}
flag[dep]=3;
dfs(dep+1,t1,t2,now);
}
void write()
{
fout=fopen("rival.out","w");
fprintf(fout,"%I64d\n",sum-ans);
fclose(fout);
}
int main()
{
init();
dfs(1,a,b,0);
write();
return 0;
}
posted on 2010-01-06 19:39
lee1r 閱讀(173)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃