UVA 12563 Jin Ge Jin Qu hao
dp-背包
开始用普通dp写了一发发现没法确定最大时间。。。
后来看到大牛机智的写法，嗯。。。dp表示当前状态能否成立；然后从条件最好的状态开始遍历，直到这个状态成立然后退出遍历。
具体的看代码吧。。。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 int dp[100][10000]; 8 int d[100]; 9 10 int main (){ 11 int T,kase=0; 12 cin>>T; 13 while (T--){ 14 int n,t; 15 cin>>n>>t; 16 for (int i=0;i<n;i++){ 17 cin>>d[i]; 18 } 19 sort (d,d+n); 20 memset (dp,0,sizeof dp); 21 dp[0][0]=1; 22 for (int k=0;k<n;k++){ 23 for (int j=t;j>=d[k];j--){ 24 for (int i=k+1;i>0;i--){ 25 if (dp[i-1][j-d[k]]) 26 dp[i][j]=1; 27 } 28 } 29 } 30 int ans=0; 31 int time; 32 int flag=0; 33 for (int i=n;i>=0;i--){ 34 for (int j=t-1;j>=0;j--){//cout<<j<<" "; 35 if (dp[i][j]){ 36 ans=i; 37 time=j; 38 flag=1; 39 break ; 40 } 41 } 42 if (flag) 43 break ; 44 } 45 cout<<"Case "<<++kase<<": "<<ans+1<<" "<<time+678<<endl; 46 } 47 return 0; 48 }