UVa-12563

最近一直在做dp的题，上周六的BC简直惨不忍睹，就做出来一道题最后还FST了。不管了，暂时还是少刷一些比赛吧。

好久没有更新了。集训结束了，太弱，没劲去写感想。在学校待到26号，然后回家，9.2再来。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn=55;
 6 int n,t;
 7 int a[maxn];
 8 int dp[maxn*180];
 9 int main()
10 {
11     int T;
12     scanf("%d",&T);
13     for(int kase=1;kase<=T;++kase)
14     {
15         scanf("%d%d",&n,&t);
16         for(int i=1;i<=n;i++)
17             scanf("%d",&a[i]);
18         int ans=0;
19         memset(dp,-1,sizeof(dp));
20         dp[0]=0;
21         for(int i=1;i<=n;i++)
22             for(int j=t-1;j>=0;j--)
23             {
24                 if(j>=a[i]&&dp[j-a[i]]>=0)
25                     dp[j]=max(dp[j],dp[j-a[i]]+1);
26                 ans=max(ans,dp[j]);
27             }
28         for(int i=t-1;i>=0;i--)
29             if(dp[i]==ans)
30             {
31                 printf("Case %d: %d %d
",kase,ans+1,i+678);
32                 break;
33             }
34     }
35 }