admin 管理员组

文章数量: 1184232

[USACO17JAN]Hoof, Paper, Scissor S

这道题首先说明了有 3 3 3 个手势 P P P , H H H , S S S。

我们可以开三个数组分别把他们记下来。

定义 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 为当前第 i i i 轮，是否用了手势，当前是 P P P 或 H H H 或 S S S。

转移方程：

f [ i ] [ j ] [ 0 ] = m a x ( f [ i ] [ j ] [ 0 ] , m a x ( f [ i − 1 ] [ j ] [ 0 ] + h [ i ] , m a x ( f [ i − 1 ] [ j − 1 ] [ 1 ] + h [ i ] , f [ i − 1 ] [ j − 1 ] [ 2 ] + h [ i ] ) ) ) ; f[i][j][0]=max(f[i][j][0],max(f[i-1][j][0]+h[i],max(f[i-1][j-1][1]+h[i],f[i-1][j-1][2]+h[i]))); f[i][j][0]=max(f[i][j][0],max(f[i−1][j][0]+h[i],max(f[i−1][j−1][1]+h[i],f[i−1][j−1][2]+h[i])));

f [ i ] [ j ] [ 1 ] = m a x ( f [ i ] [ j ] [ 1 ] , m a x ( f [ i − 1 ] [ j ] [ 1 ] + s [ i ] , m a x ( f [ i − 1 ] [ j − 1 ] [ 0 ] + s [ i ] , f [ i − 1 ] [ j − 1 ] [ 2 ] + s [ i ] ) ) ) ; f[i][j][1]=max(f[i][j][1],max(f[i-1][j][1]+s[i],max(f[i-1][j-1][0]+s[i],f[i-1][j-1][2]+s[i]))); f[i][j][1]=max(f[i][j][1],max(f[i−1][j][1]+s[i],max(f[i−1][j−1][0]+s[i],f[i−1][j−1][2]+s[i])));

f [ i ] [ j ] [ 2 ] = m a x ( f [ i ] [ j ] [ 2 ] , m a x ( f [ i − 1 ] [ j ] [ 2 ] + p [ i ] , m a x ( f [ i − 1 ] [ j − 1 ] [ 0 ] + p [ i ] , f [ i − 1 ] [ j − 1 ] [ 1 ] + p [ i ] ) ) ) ; f[i][j][2]=max(f[i][j][2],max(f[i-1][j][2]+p[i],max(f[i-1][j-1][0]+p[i],f[i-1][j-1][1]+p[i]))); f[i][j][2]=max(f[i][j][2],max(f[i−1][j][2]+p[i],max(f[i−1][j−1][0]+p[i],f[i−1][j−1][1]+p[i])));

( 1 ≤ i ≤ n ) \left( 1 \leq i \leq n \right) (1≤i≤n)
( 0 ≤ j ≤ 1 ) \left( 0 \leq j \leq 1 \right) (0≤j≤1)

最后的答案为

a n s = max ⁡ ( f [ n ] [ i ] [ 0 ] , max ⁡ ( f [ n ] [ i ] [ 1 ] , f [ n ] [ i ] [ 2 ] ) ) ) ; ans=\max(f[n][i][0],\max(f[n][i][1],f[n][i][2]))); ans=max(f[n][i][0],max(f[n][i][1],f[n][i][2]))); ( 0 ≤ i ≤ 1 ) \left( 0 \leq i \leq 1 \right) (0≤i≤1)

代码:

#include<bits/stdc++.h>
using namespace std;
int n;
int p[100005];
int h[100005];
int s[100005];
int f[100005][25][3];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){char tmp;cin>>tmp;if(tmp=='P')p[i]=1;if(tmp=='H')h[i]=1;if(tmp=='S')s[i]=1;}f[1][0][0]=h[1];f[1][0][1]=s[1];f[1][0][2]=p[1];for(int i=1;i<=n;i++)for(int j=0;j<=1;j++){f[i][j][0]=max(f[i][j][0],max(f[i-1][j][0]+h[i],max(f[i-1][j-1][1]+h[i],f[i-1][j-1][2]+h[i])));f[i][j][1]=max(f[i][j][1],max(f[i-1][j][1]+s[i],max(f[i-1][j-1][0]+s[i],f[i-1][j-1][2]+s[i])));f[i][j][2]=max(f[i][j][2],max(f[i-1][j][2]+p[i],max(f[i-1][j-1][0]+p[i],f[i-1][j-1][1]+p[i])));}int ans=0;for(int i=0;i<=1;i++)ans=max(ans,max(f[n][i][0],max(f[n][i][1],f[n][i][2])));printf("%d",ans);return 0;
}

本文标签： USACO17JANHoof Paper Scissor S

版权声明：本文标题：[USACO17JAN]Hoof, Paper, Scissor S 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1699066776a326040.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。