首页 > 代码库 > SPOJ ROCK

SPOJ ROCK

DP题,这题居然是1星题!!太大打击了

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 #define N 205 5 char s[N]; 6 int sum[N][2],dp[N]; 7 int main(){ 8     int t,l,sum0,sum1; 9     scanf("%d",&t);10     while(t--){11         scanf("%d",&l);12         getchar();13         scanf("%s",s+1);14         sum[0][0]=sum[0][1]=0;15         for(int i=1;i<=l;i++){16             sum[i][0]=sum[i-1][0];17             sum[i][1]=sum[i-1][1];18             sum[i][s[i]-0]++;19         }20         dp[0]=0;21         for(int i=1;i<=l;i++){22             for(int j=1;j<=i;j++){23                 sum0=sum[i][0]-sum[j-1][0];24                 sum1=sum[i][1]-sum[j-1][1];25                 if(sum1<=sum0)continue;26                 dp[i]=max(dp[i],dp[j-1]+i-j+1);27             }28         }29         printf("%d\n",dp[l]);30     }31     return 0;32 }