极度郁闷地完成了这一题……倒不是因为名字是“情敌”，而是我的测评系统似乎出了问题，导致我一直60分。后来把文件复制一份，新建文件夹，重新测评，100！当时快气爆了！
此题的方法是搜索+DP
如果忽略“超级情敌”不管，发现这是个二维费用的背包。超级情敌最多有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 阅读(162)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划