A题： Yougth's Game[Ⅲ]（ 区间dp ）
这是在省赛前热身赛出的题目，可能是题目中实用到博弈的思想，非常多人都在做，并且在尝试暴力。
可是没有人往dp的方向上想。
- 题目类型：动态规划+博弈
- 分析：题意描写叙述的非常清楚，就是选择在两端取数，当前取的数不仅可以影响下一次的结果，并且可以影响后面的结果。
。
。又是一个求最优值，那么是不是可以往dp的方向上想了。区间dp
- 定义状态dp[ i ] [ j ] 为从 i 到 j 上A的得分，那么B的得分就是sum（i,j）-dp[ i ] [ j ]
- 转移方程 : dp[i][j]=max(dp[i][j],a[i]+(sum[j]-sum[i]-dp[i+1][j])); 表示区间i--j取第一个
- dp[i][j]=max(dp[i][j],a[j]+(b[j-1]-b[i-1]-dp[i][j-1])); 表示区间i--j取最后一个
-
代码：
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1200; int a[N],dp[N][N],n; int b[N]; int main() { while(~scanf("%d",&n)&&n) { b[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=b[i-1]+a[i]; } for(int l=1;l<=n;l++) { for(int i=1,j=l;j<=n;i++,j++) { dp[i][j]=-99999999; dp[i][j]=max(dp[i][j],a[i]+(b[j]-b[i]-dp[i+1][j])); dp[i][j]=max(dp[i][j],a[j]+(b[j-1]-b[i-1]-dp[i][j-1])); } } printf("%d ",dp[1][n]-(b[n]-dp[1][n])); } return 0; }
-
E：Yougth's Game[II]
题目类型：组合博弈事实上就是一个sg函数，sg函数解说：解说
分析：题目能够抽象成一个取石子游戏，三堆石子x，y，x*y。那么就抽象成了经典的取石子游戏。每次能够取得数目是给定的，谁最后取完谁赢。求出三个数的sg值，然后异或就是ans
代码：#include<stdio.h> #include<string.h> #include <string> #include <iostream> using namespace std; const int N = 10008; int s[108],t; int sg[N]; bool hash[N]; void sg_solve(int *s,int t,int N) //N求解范围 S[]数组是能够每次取的值。t是s的长度。 { int i,j; memset(sg,0,sizeof(sg)); for(i=1;i<=N;i++) { memset(hash,0,sizeof(hash)); for(j=0;j<t;j++) if(i - s[j] >= 0) hash[sg[i-s[j]]] = 1; for(j=0;j<=N;j++) if(!hash[j]) break; sg[i] = j; } } int main() { int x,y; while(~scanf("%d%d",&x,&y)) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&s[i]); sg_solve(s,n,N); if((sg[x]^sg[y]^sg[x*y])==0) printf("Yougth is best "); else printf("No "); } return 0; }
H题：合并游戏
题目类型：状态压缩动态规划
分析：给出每两个石子合并蹦出的金币，求全部石子合并之后蹦出的金币，分析能够发现不同的合并顺序会有不一样的结果。然后满足最优子结构的性质。那就是确定某几个石子合并的到的最大金币永远是确定的，那么我们能够用dp来求解。而这个题目恰好是一个从0到全部合并的一个过程。用二进制压缩来表示状态。
定义状态：dp【st】表示状态st中为1的合并起来的最大值
状态转移方程：dp[state-(1<<j)]=max(dp[state-(1<<j)], dp[state]+a[i][j]);（每次都从 i 为1的点转移过来）
代码： -
-
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 12; int a[N][N],dp[1<<N]; int main() { int n; while(~scanf("%d",&n)&&n) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]); memset(dp,0,sizeof(dp)); for(int state=(1<<n); state>=0; state--) { for(int i=0; i<n; i++) //枚举初始合并点 { if(state&(1<<i)) continue; for(int j=0; j<n; j++) //跟哪一个合并 { if(!(state&(1<<j))) continue; if(i==j) continue; int newstate=state-(1<<j); dp[newstate]=max(dp[newstate], dp[state]+a[i][j]); } } } int maxnum=0; for(int i=0; i<(1<<n); i++) maxnum=max(maxnum, dp[i]); printf("%d ", maxnum); } return 0; }