地址：http://www.51nod.com/Challenge/Problem.html#!#problemId=1657 思路：DP. 好久没做题了，改改删删做了2个多小时，没想到一次就AC了(￣▽￣)~* dp[i][j]:表示以第i个'T'结尾的字符串中改变j个'T'时的最大价值。 首先预处理出每个'T'影响的'F'个数为到下一个'T'之间的'F'个数，记为d[i],(d[0]为第一个'T'前的‘F’个数) 我们设开始时的朝向为正轴，那么对于dp[i][j]需要求其最大值和最小值（为负） 以最大值来说，在dp[i][j]时，当前位的值仅仅与(i-j)有关,当(i-j)%2==1时是减去d[i]，反之为加上d[i] 那么对于(i-j)%2==1, dp[i][j]=max(dp[i-1][j]-d[i],dp[i-1][j-1]-d[i]-1) (i-j)%2==0, dp[i][j]=max(dp[i-1][j]+d[i],dp[i-1][j-1]+d[i]+1) n个改变，ans=dp[m][n]，而有些情况改变n-1个即dp[m][n-1]更大，例如 FFTFTFFTFF   n=2 而对于最小值同理 Code: #include using namespace std; const int MAX_N=55; const int MAX_S=105; int n; int d[MAX_S]; int dp[MAX_S][MAX_N]; string str; int main() { ios::sync_with_stdio(false); cin>>str>>n; int len=str.length(),m=0,ans=0;; int l=0,t; while(llen) --m; } if(n>=m) ans=len-(n-m)%2; else{ dp[0][0]=d[0]; for(int i=1;i<=m;++i) { if(i%2) dp[i][0]=dp[i-1][0]-d[i]; else dp[i][0]=dp[i-1][0]+d[i]; for(int j=1;j<=i&&j<=n;++j) if((i-j)%2){ dp[i][j]=dp[i-1][j-1]-d[i]-1; if(i-1>=j) dp[i][j]=max(dp[i][j],dp[i-1][j]-d[i]); }else{ dp[i][j]=dp[i-1][j-1]+d[i]+1; if(i-1>=j) dp[i][j]=max(dp[i][j],dp[i-1][j]+d[i]); } } ans=max(ans,max(dp[m][n],dp[m][n-1]-1)); for(int i=1;i<=m;++i) { if(i%2) dp[i][0]=dp[i-1][0]-d[i]; else dp[i][0]=dp[i-1][0]+d[i]; for(int j=1;j<=i&&j<=n;++j) if((i-j)%2){ dp[i][j]=dp[i-1][j-1]-d[i]-1; if(i-1>=j) dp[i][j]=min(dp[i][j],dp[i-1][j]-d[i]); }else{ dp[i][j]=dp[i-1][j-1]+d[i]+1; if(i-1>=j) dp[i][j]=min(dp[i][j],dp[i-1][j]+d[i]); } } ans=max(ans,max(-dp[m][n],-dp[m][n-1]+1)); } cout<