普及组dp.
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100050 using namespace std; int n,k,dp[maxn][21][4],p[maxn],map[5][5]; char s[5]; int main() { map[2][1]=map[3][2]=map[1][3]=1; scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) { scanf("%s",s); if (s[0]=='P') p[i]=2; else if (s[0]=='S') p[i]=3; else p[i]=1; } for (int i=1;i<=n;i++) { dp[i][0][1]=dp[i-1][0][1]+map[1][p[i]]; dp[i][0][2]=dp[i-1][0][2]+map[2][p[i]]; dp[i][0][3]=dp[i-1][0][3]+map[3][p[i]]; } for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) { dp[j][i][1]=max(dp[j-1][i][1],max(dp[j-1][i-1][2],dp[j-1][i-1][3]))+map[1][p[j]]; dp[j][i][2]=max(dp[j-1][i][2],max(dp[j-1][i-1][1],dp[j-1][i-1][3]))+map[2][p[j]]; dp[j][i][3]=max(dp[j-1][i][3],max(dp[j-1][i-1][1],dp[j-1][i-1][2]))+map[3][p[j]]; } printf("%d ",max(dp[n][k][1],max(dp[n][k][2],dp[n][k][3]))); return 0; }