ECNA 2018 H Sequential Yagtzee(模拟+dp)

题意是按照顺序Yahtzee的游戏规则，已知投骰子的结果序列，求游戏的最大得分。
虽然是一看就想跑路的模拟题，然后会发现其实不难写。把计分模拟一下，然后dp出最大得分就可以了。

我们设dp[i][j]表示完成第i项规则，用了j个骰子的最大得分。那么转移时有dp[i][j+k]=max(dp[i][j+k],dp[i-1][j]+score(i,j,k))，只要求得score(i,j,k)，即用j之后k个骰子(5<=k<=15)，使之满足第i个规则的最大得分。
由于k比较小，可以暴力枚举换掉哪些骰子再掷一次情况的得分。枚举次数不超过2^10。

```
/*
```
```
Author: fffasttime
```
```
Date: 2019/07/23 17:00
```
```
*/
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
const int N=100010;
```
```
 
```
```
int seq[250], dp[14][250],step,s0;
```
```
int cnt[6];
```
```
 
```
```
int getscore(int f[]){
```
```
	memset(cnt,0,sizeof cnt);
```
```
	inc(i,5) cnt[f[i]-1]++;
```
```
	if (step<=6) return step*cnt[step-1];
```
```
	else if (step==7){
```

		inc(i,6) if(cnt[i]>=3) return accumulate(f,f+5,0);

```
	}
```
```
	else if (step==8){
```

		inc(i,6) if(cnt[i]>=4) return accumulate(f,f+5,0);

```
	}
```
```
	else if (step==9){
```

		if (any_of(cnt,cnt+6,[](int x){return x==3;}) && any_of(cnt,cnt+6,[](int x){return x==2;}))

```
			return 25;
```
```
	}
```
```
	else if (step==10){
```

		inc(i,3) if (all_of(cnt+i,cnt+i+4,[](int x){return x;})) return 30;

```
	}
```
```
	else if (step==11){
```

		inc(i,2) if (all_of(cnt+i,cnt+i+5,[](int x){return x;})) return 40;

```
	}
```
```
	else if (step==12){
```
```
		return accumulate(f,f+5,0);
```
```
	}
```
```
	else if (step==13){
```

		if (any_of(cnt,cnt+6,[](int x){return x==5;})) return 50;

```
	}
```
```
	return 0;
```
```
}
```
```
 
```
```
void dfs(int s, int f[], int d){
```

	dp[step][s]=max(dp[step][s],getscore(f)+dp[step-1][s0]);

```
	if (d==2) return;
```
```
	int cur[5];
```
```
	for (int i=1;i<32;i++){
```
```
		int us=s;
```
```
		copy(f,f+5,cur);
```
```
		for (int j=0;j<5;j++) if(i>>j&1)
```
```
			cur[j]=seq[us++];
```
```
		dfs(us,cur,d+1);
```
```
	}
```
```
}
```
```
 
```
```
void solve(int s){
```
```
	int f[5];
```
```
	for (int i=0;i<5;i++) f[i]=seq[s+i];
```
```
	dfs(s+5,f,0);
```
```
}
```
```
 
```
```
int main(){
```
```
	fill(seq,seq+220,1);
```
```
	int n; cin>>n;
```
```
	inc(i,n) scanf("%d",seq+i);
```
```
	for (step=1;step<=13;step++){
```

		for (int j=(step-1)*5;(j<=(step-1)*15) && j<=n;j++){

```
			s0=j;
```
```
			solve(j);
```
```
		}
```
```
	}
```

	cout<<*max_element(dp[13],dp[13]+n+1)<<'\n';

```
	return 0;
```
```
}
```

发表评论 取消回复

发表评论取消回复