广州网站设计网站制作,wordpress首页文章显示分类,四川省乐山市建设银行网站,东昌府聊城做网站公司1388. 游戏 - AcWing题库
所需知识#xff1a;博弈论#xff0c;区间dp
由于双方都采取最优的策略来取数字#xff0c;所以结果为确定的#xff0c;有可能会有多个不同的过程#xff0c;但是我们只需要关注最终结果就行了。
方法一#xff1a;
定义dp[i][j] 表示区间…1388. 游戏 - AcWing题库
所需知识博弈论区间dp
由于双方都采取最优的策略来取数字所以结果为确定的有可能会有多个不同的过程但是我们只需要关注最终结果就行了。
方法一
定义dp[i][j] 表示区间i到j中先手能取得的最大值依次遍历区间最后判断最大值因为区间长度长的来源必定是区间长度短的所以我们可以第一层遍历区间的长度第二层遍历区间的左端点。
状态转移方程式dp[i][j]max(w[i]s[j]-s[i]-dp[i1][j],w[j]s[j-1]-s[i-1]-dp[i][j-1]);
对于状态转移方程式的解释
若选择左边的数字则下一个人在i1到j中选择对于他自己而言的最优解所以dp[i][j] 为w[i] s[j]-s[i] (i1到j的区间和) -dp[i1][j](减去下一个人能拿的最大值)。
若选择右边的数字则下一个人在i到j-1中选择对于他自己而言的最优解所以dp[i][j] 为w[j] s[j-1]-s[i-1] (i到j-1的区间和) -dp[i][j-1](减去下一个人能拿的最大值)。
最后取最大值即为答案。
C代码
#include iostream
#include cstring
#include algorithmusing namespace std;int N;
int dp[105][105];
int w[105],s[105];
int main()
{cinN;for (int i 1; i N; i ){cinw[i];s[i]s[i-1]w[i];}for(int len1;lenN;len){for(int i1;iN;i){int jilen-1;dp[i][j]max(w[i]s[j]-s[i]-dp[i1][j],w[j]s[j-1]-s[i-1]-dp[i][j-1]);}}coutdp[1][N] s[N]-dp[1][N];return 0;
}
方法二
定义dp[i][j] 表示在区间i到j内先手能拿到的最优值减去后手拿的最优值即为A-BA为方法一中的区间最大值B为区间和减最大值
遍历方法仍和方法一一样先遍历一遍区间长度然后再遍历左端点的值。
状态转移方程式dp[i][j]max(w[i]-dp[i1][j],w[j]-dp[i][j-1]);
对于状态转移方程式的解释
若取左边的数,则下一个人在区间i1到j中取dp[i1][j]表示该区间中的maxB-A所以-dp[i1][j]表示该区间中A-B的最大值在加上w[i],表示区间i到j中A-B的最大值
同理若取右边的数,则下一个人在区间i到j-1中取dp[i][j-1]表示该区间中的maxB-A所以-dp[i][j-1]表示该区间中A-B的最大值在加上w[j],表示区间i到j中A-B的最大值
最后dp[1][N]表示该区间内A-B的最大值又因为ABsumsum为所有元素和
联立两个方程解得Adp[1][N]sum/2;B(sum-dp[1][N])/2;
C代码
#include iostream
#include cstring
#include algorithmusing namespace std;int N;
int dp[105][105];
int w[105],s[105];
int sum0;
int main()
{cinN;for (int i 1; i N; i ){cinw[i];sumw[i];}for(int len1;lenN;len){for(int i1;ilen-1N;i){int jilen-1;dp[i][j]max(w[i]-dp[i1][j],w[j]-dp[i][j-1]);}}cout(sumdp[1][N])/2 (sum-dp[1][N])/2;return 0;
}
