首页 > 代码库 > UVa12563- Jin Ge Jin Qu hao

UVa12563- Jin Ge Jin Qu hao

思路一定要清晰!

技术分享
/* * Author:  Bingo * Created Time:  2014/12/25 3:45:35 * File Name: uva12563.cpp */#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <stack>#include <queue>#include <set>#include <time.h>using namespace std;const int maxint = -1u>>1;int main(){    int T;    int c=1;    cin>>T;    while(T--){        int n,time;        cin>>n>>time;        int f[n+1][180*n+700];        int anss[n+1][180*n+700];        memset(anss,0,sizeof(anss));        memset(f,0,sizeof(f));        int v;        for (int i=1;i<=n;i++){            scanf("%d",&v);            for (int j=0;j<=time-1;j++){                f[i][j]=(i==1?0:f[i-1][j]);                anss[i][j]=(i==1?0:anss[i-1][j]);                if (j>=v)if (f[i][j]<=f[i-1][j-v]+1){                    if (f[i][j]==f[i-1][j-v]+1) anss[i][j]=max(anss[i][j],anss[i-1][j-v]+v);                    else anss[i][j]=anss[i-1][j-v]+v;                    f[i][j]=f[i-1][j-v]+1;                }            }        }        cout<<"Case "<<c<<": ";        c++;        cout<<f[n][time-1]+1<<" "<<anss[n][time-1]+678<<endl;    }    return 0;}
View Code

 

UVa12563- Jin Ge Jin Qu hao