度度熊的午饭时光

题目描述

度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。 百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。 但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)

题目分析

这一道题就是典型的背包DP。 我们可以设一下bz[i]这个布尔数组为是否能刚好用掉i元钱，然后用一个辅助布尔数组，bz2[i][j]表示在刚好花掉i元钱，最优方案的时候第j个菜是否会被选中。 接着我们便会得到一个转移方程。 如果bz[i-c[j]]的方案比bz[i]好， bz2[i]=bz2[j]。 但问题是，我们怎么判断bz[i-c[j]]的方案是否会比bz[i]好呢？ 首先我们先判断一下他们的分数（注意，bz[i-c[j]]的所有分数和加起来后还要加是s[j]！），如果分数相同，我们就看一下他们的编号和（也别忘了加j！）如果编号和相同，我们就看一下他们的字典序是否相等，哪个更小就选哪一个。 最后选择所有方案中最优的方案。

代码

#include<cstdio> #include<cstring> using namespace std; bool bk[1100][110],bz[1100]; int s[1100],c[1100]; int b,n; int sum7[110],sum8[110]; int ans3[110]; int mymin(int x,int y) {return x<y?x:y;} void insert(int cost,int id) { if(bz[cost]==false) { bz[cost]=true; for(int i=1;i<=n;i++) { bk[cost][i]=bk[cost-c[id]][i]; } bk[cost][id]=true; return ; } if(bk[cost-c[id]][id]==true) { return ; } int sum=0,sum2=0,sum3=0,sum4=0,sum5=0,sum6=0; for(int i=1;i<=n;i++) { if(bk[cost-c[id]][i]==true) { sum+=i; sum3+=s[i]; sum5++; sum7[sum5]=i; } if(bk[cost][i]==true) { sum2+=i; sum4+=s[i]; sum6++; sum8[sum6]=i; } } sum5++; sum7[sum5]=id; bool bk2=false; if(sum+id<sum2) bk2=true; if(sum+id==sum2) { bool bz2=false; for(int i=1;i<=mymin(sum5,sum6);i++) { if(sum7[i]<sum8[i]) { bz2=true; bk2=true; break; } if(sum7[i]>sum8[i]) { bz2=true; break; } } if(bz2==true&&sum5>sum6) { bk2=true; } } if(sum3+s[id]>sum4||(bk2==true&&sum3+s[id]==sum4)) { for(int i=1;i<=n;i++) { bk[cost][i]=bk[cost-c[id]][i]; } bk[cost][id]=true; } return ; } int main() { freopen("d.in","r",stdin); freopen("d.out","w",stdout); int t,t2=0; scanf("%d",&t); while(t--) { scanf("%d",&b); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&s[i],&c[i]); } memset(bz,false,sizeof(bz)); memset(bk,false,sizeof(bk)); bz[0]=true; for(int i=1;i<=n;i++) { for(int j=b;j>=c[i];j--) { if(bz[j-c[i]]==true) { insert(j,i); } } } int ans=-1,ans2; for(int i=0;i<=b;i++) { int sum9=0; for(int j=1;j<=n;j++) { if(bk[i][j]==true) { sum9+=s[j]; } } bool bk2=false; if(sum9==ans) { int sum=0,sum2=0,sum3=0,sum4=0,sum5=0,sum6=0; for(int j=1;j<=n;j++) { if(bk[i][j]==true) { sum+=j; sum3+=s[j]; sum5++; sum7[sum5]=j; } if(bk[ans2][j]==true) { sum2+=j; sum4+=s[j]; sum6++; sum8[sum6]=j; } } if(sum<sum2) bk2=true; if(sum==sum2) { bool bz2=false; for(int j=1;j<=mymin(sum5,sum6);j++) { if(sum7[j]<sum8[j]) { bz2=true; bk2=true; break; } if(sum7[j]>sum8[j]) { bz2=true; break; } } if(bz2==false&&sum5>sum6) { bk2=true; } } } if(sum9>ans||(sum9==ans&&bk2==true)) { ans=sum9; ans2=i; } } printf("Case #%d:\n",++t2); printf("%d %d\n",ans,ans2); int len=0; for(int i=1;i<=n;i++) { if(bk[ans2][i]==true) { len++; ans3[len]=i; } } for(int i=1;i<=len;i++) { if(i<len) printf("%d ",ans3[i]); else printf("%d\n",ans3[i]); } } return 0; }