中矿大 C 石头剪刀布【决策DP*待看/codeforces原题】
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
齐齐和司机正在玩剪刀石头布，不过他俩有些玩腻了，所以思考了一个全新的“剪刀石头布”的游戏。
全新的“剪刀石头布“”的胜负规则和剪刀石头布一样，每人有3种手势，分别为剪刀（scissors）、石头（rock）、布（paper）。剪刀胜于布，布胜于石头，石头胜于剪刀，当手势相同时为平局。
齐齐可以在司机出手势后再出自己的手势，但是不能连续两局出同一种手势。
他们一共进行n盘对局。每一盘中，胜者+1分，败者-1分，平局两人都不扣分。
已知司机的n局的出手势情况，求齐齐进行n盘对局后获得的最高分数。
输入描述:
第1行输入一个整数n，代表进行n盘对局。
第2-n+1行，每行输入一个字符串，为“scissors”、“rock”、“paper”之一，代表司机第i盘对局的手势情况。
数据保证：1≤n≤106
输出描述:
输出一行结果，代表齐齐进行n盘对局后获得的最高分数。
示例1
输入
3 rock paper scissors
输出
3
说明
齐齐可以第1盘出“paper”，第2盘出“scissors”，第3盘出“rock”，最高分数3分。
示例2
输入
2 rock rock
输出
1
说明
齐齐可以第1盘出“paper”，第2盘出“rock”，最高分数1分。
【分析】：
【代码】：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[10000001][3] = {0}; int n = 0; int s[1000001] = {0}; inline int getScole(int a,int b) { if(a==2&&b==1) return 1; if(a==1&&b==2) return -1; if(a==1&&b==0) return 1; if(a==0&&b==1) return -1; if(a==0&&b==2) return 1; if(a==2&&b==0) return -1; return 0; } int main() { cin>>n; for(int i=1;i<=n;i++) { char ss[10]; cin>>ss; if(strcmp(ss,"scissors") == 0) { s[i]=2; } else if(strcmp(ss,"paper") == 0) { s[i]=1; } else if(strcmp(ss,"rock") == 0) { s[i]=0; } } dp[1][0]=getScole(0,s[1]); dp[1][1]=getScole(1,s[1]); dp[1][2]=getScole(2,s[1]); for(int i=2;i<=n;i++) { for(int j=0;j<3;j++) { dp[i][j]=max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+getScole(j,s[i]); } } cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<endl; return 0; }
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<fstream>//石头1 剪刀2 布3 #include<cmath> #include<algorithm>//while(r<l) using namespace std; int a[1111111]; int dp1[1111111]; int dp2[1111111]; int dp3[1111111]; char s[11]; int main() { int n; int ans=0; cin>>n; memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(dp3,0,sizeof(dp3)); for(int i=0;i<n;i++) { cin>>s; if(s[0]=='r') a[i]=1; if(s[0]=='s') a[i]=2; if(s[0]=='p') a[i]=3; if(a[i]==1) { dp3[i]+=1; dp2[i]-=1; if(i!=0) { dp3[i]+=max(dp2[i-1],dp1[i-1]); dp2[i]+=max(dp3[i-1],dp1[i-1]); dp1[i]+=max(dp2[i-1],dp3[i-1]); } } if(a[i]==2) { dp1[i]+=1; dp3[i]-=1; if(i!=0) { dp3[i]+=max(dp2[i-1],dp1[i-1]); dp2[i]+=max(dp3[i-1],dp1[i-1]); dp1[i]+=max(dp2[i-1],dp3[i-1]); } } if(a[i]==3) { dp2[i]+=1; dp1[i]-=1; if(i!=0) { dp3[i]+=max(dp2[i-1],dp1[i-1]); dp2[i]+=max(dp3[i-1],dp1[i-1]); dp1[i]+=max(dp2[i-1],dp3[i-1]); } } } cout<<max(max(dp1[n-1],dp2[n-1]),dp3[n-1]); return 0; }