中矿大 C 石头剪刀布【决策DP*待看/codeforces原题】

时间限制：C/C++ 1秒，其他语言2秒
空间限制：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

输出

说明

齐齐可以第1盘出“paper”，第2盘出“scissors”，第3盘出“rock”，最高分数3分。

示例2

输入

2

rock

rock

输出

说明

齐齐可以第1盘出“paper”，第2盘出“rock”，最高分数1分。

【分析】：

【代码】：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int dp[][] = {};

int n = ;

int s[] = {};

inline int getScole(int a,int b)

{

    if(a==&&b==) return ;

    if(a==&&b==) return -;

    if(a==&&b==) return ;

    if(a==&&b==) return -;

    if(a==&&b==) return ;

    if(a==&&b==) return -;

    return ;

}

int main()

{

    cin>>n;

    for(int i=;i<=n;i++)

    {

        char ss[];

        cin>>ss;

        if(strcmp(ss,"scissors") == )

        {

            s[i]=;

        }

        else if(strcmp(ss,"paper") == )

        {

            s[i]=;

        }

        else if(strcmp(ss,"rock") == )

        {

            s[i]=;

        }

    }

    dp[][]=getScole(,s[]);

    dp[][]=getScole(,s[]);

    dp[][]=getScole(,s[]);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<;j++)

        {

            dp[i][j]=max(dp[i-][(j+)%],dp[i-][(j+)%])+getScole(j,s[i]);

        }

    }

    cout<<max(max(dp[n][],dp[n][]),dp[n][])<<endl;

    return ;

}

#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[];

int dp1[];

int dp2[];

int dp3[];

char s[];

int main()

{

    int n;

    int ans=;

    cin>>n;

    memset(dp1,,sizeof(dp1));

    memset(dp2,,sizeof(dp2));

    memset(dp3,,sizeof(dp3));

    for(int i=;i<n;i++)

    {

        cin>>s;

        if(s[]=='r') a[i]=;

        if(s[]=='s') a[i]=;

        if(s[]=='p') a[i]=;

        if(a[i]==)

        {

            dp3[i]+=;

            dp2[i]-=;

            if(i!=)

            {

                dp3[i]+=max(dp2[i-],dp1[i-]);

                dp2[i]+=max(dp3[i-],dp1[i-]);

                dp1[i]+=max(dp2[i-],dp3[i-]);

            }

        }

        if(a[i]==)

        {

            dp1[i]+=;

            dp3[i]-=;

            if(i!=)

            {

                dp3[i]+=max(dp2[i-],dp1[i-]);

                dp2[i]+=max(dp3[i-],dp1[i-]);

                dp1[i]+=max(dp2[i-],dp3[i-]);

            }

        }

        if(a[i]==)

        {

            dp2[i]+=;

            dp1[i]-=;

            if(i!=)

            {

                    dp3[i]+=max(dp2[i-],dp1[i-]);

                dp2[i]+=max(dp3[i-],dp1[i-]);

                dp1[i]+=max(dp2[i-],dp3[i-]);

            }

        }

    }

        cout<<max(max(dp1[n-],dp2[n-]),dp3[n-]);

    return ;

}

巴特西

中矿大 C 石头剪刀布【决策DP*待看/codeforces原题】

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

最新文章

热门文章