2017"百度之星"程式設計大賽 - 資格賽:1004 度度熊的午飯時光

題目：

Problem Description

度度熊最期待每天的午飯時光，因為早飯菜品清淡，晚飯減肥不敢吃太多（胖紙的憂傷T.T）。

百度食堂的午餐超級豐富，祖國各大菜系應有盡有，度度熊在每個視窗都有愛吃的菜品，而且他還為喜愛的菜品打了分，吃貨的情懷呀(>.<)。

但是，好吃的飯菜總是很貴，每天的午飯預算有限，請幫度度熊算一算，怎樣打飯才能買到的最好吃的飯菜?(不超過預算、不重樣、午餐等分最高的情況下，選擇菜品序号加和最小，加和相等時字典序最小的組合)

Input

第一行一個整數T，表示T組資料。每組測試資料将以如下格式從标準輸入讀入：

B

N

score_1 cost_1

score_2 cost_2

:

score_N cost_N

第一行，正整數B（0 <= B <= 1000），代表午餐的預算。

第二行，正整數N (0 <= N <= 100)，代表午餐可選的菜品數量

從第三行到第 (N + 2) 行，每行兩個正整數，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的價格(0 <= score_i, cost_i <= 100)。

Output

對于每組資料，輸出兩行：第一行輸出："Case #i:"。i代表第i組測試資料。第二行輸出菜品的總得分和總花費，以空格分隔。第三行輸出所選菜品的序号，菜品序号從1開始，以空格分隔。

Sample Input

2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12      

Sample Output

Case #1:
34 29
2 3 5 6
Case #2:
0 0
      

思路：0-1背包+記錄路徑。由于不會記錄路徑，在網上找了下模闆套進去，然後開始了無限WA之旅。。。 然後在和其他人交流中發現了很多不能過的資料，改來又改去，比如B=0時，也是有總得分的（就是那些cost=0，score!=0的菜），真的心塞塞。。。發現一些人有的資料過不了也AC了，容我吐槽一下題目資料，感覺打代碼運氣很重要

萬一不小心就水過去呢

CODE：

#include<bits/stdc++.h>
using namespace std;
int w[],v[],dp[][],x[],vis[][];
int main()
{
        int t,n,m,i,j,op=;
        scanf("%d",&t);
        while(t--){
                scanf("%d%d",&m,&n);
                int z=;
                for(i=;i<=n;i++){
                        scanf("%d%d",&v[i],&w[i]);
                        if(!w[i]) z+=v[i];
                }
                if(!m&&z){
                        printf("Case #%d:\n%d 0\n",op++,z);
                        int zz=;
                        for(i=;i<=n;i++){
                                if(!w[i]&&v[i]){
                                        if(zz) printf(" ");
                                        printf("%d",i);
                                        zz=;
                                }
                        }
                        puts("");
                        continue;
                }
                if(!n||!m){
                        printf("Case #%d:\n0 0\n",op++);
                        continue;
                }
                memset(dp,,sizeof(dp));
                memset(x,,sizeof(x));
                memset(vis,,sizeof(vis));
                int cnt=;
                for(i=;i<=n;i++){
                        for(j=;j<=m;j++){
                                dp[i][j]=dp[i-][j];
                                if(j>=w[i]&&dp[i][j]<dp[i-][j-w[i]]+v[i]){
                                        dp[i][j]=dp[i-][j-w[i]]+v[i];
                                        vis[i][j]=;
                                }
                        }
                }
                int V=m;
                for(i=n;i>;i--) if(vis[i][V]) x[i]=,cnt+=w[i],V-=w[i];
                printf("Case #%d:\n%d %d\n",op++,dp[n][m],cnt);
                if(cnt){
                        j=;
                        for(i=;i<=n;i++){
                                if(!x[i]) continue;
                                if(j) printf(" ");
                                printf("%d",i);
                                j=;
                        }
                        puts("");
                }
        }
        return ;
}