2015 Multi-University Training Contest 10

加一维0和1表示有没有拿过这种糖。

然后完全背包滚动数组过去就可以了。

然而实际上不用加这一维。直接先0-1再完全就可以了。

因为第一个的时候收益是a+b。后面的收益是a。

如果第一个都不拿。后面自然不会拿了。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 int dp[2001][2];
 7 
 8 int main(void)
 9 {
10     int T; cin>>T;
11     while(T--)
12     {
13         int M,N; scanf("%d%d",&M,&N);
14         memset(dp,0,sizeof(dp));
15         for(int i=1;i<=N;i++)
16         {
17             int w,a,b;
18             scanf("%d%d%d",&w,&a,&b);
19             for(int j=0;j<=M;j++) dp[j][0]=max(dp[j][0],dp[j][1]);
20             for(int j=M;j>=w;j--) dp[j][1]=dp[j-w][0]+a+b;
21             for(int j=w;j<=M;j++) dp[j][1]=max(dp[j][1],dp[j-w][1]+a);
22         }
23         printf("%d
",max(dp[M][0],dp[M][1]));
24     }
25     return 0;
26 }

Aguin

1006 CRB and Puzzle

1007 CRB and Queries

1008 CRB and Roads

1009 CRB and String

保证s是t的子序列。

如果t的前k个字母是一样的。s的前k个也要是这个字母。

满足两条即可。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 # define maxn 100100
 6 char s[maxn],t[maxn];
 7 
 8 int main(void)
 9 {
10     int T; cin>>T;
11     while(T--)
12     {
13         scanf("%s%s",s+1,t+1);
14         int slen=strlen(s+1),tlen=strlen(t+1);
15         int ok=1,pos=1,len=1;
16         for(int i=1;i<=tlen;i++)
17         {
18             if(t[i]!=t[1]) break;
19             len=i;
20         }
21         for(int i=1;i<=len;i++) if(s[i]!=t[1]) {ok=0;break;}
22         for(int i=1;i<=tlen;i++)
23         {
24             if(s[pos]==t[i]) pos++;
25             if(pos>slen) break;
26         }
27         if(pos<=slen) ok=0;
28         puts(ok?"Yes":"No");
29     }
30     return 0;
31 }

Aguin

1010 CRB and Substrings

1011 CRB and Tree