上海计算机学会2024年3月月赛C++乙组T1数字博弈
发布时间
阅读量：
阅读量
数字博弈
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个数列 a1,a2,…,an，小爱与小艾交替取走一个数字，小爱先取。两人取数时，都只能挑选当时数列的首项或末项。取数是必须要完成的动作，不能不取，直到所有的数字都被取走为止。
游戏目的是看谁拿走的数字之和最大。两人都是非常聪明的，他们都会采用最佳的策略让自己取到的数字之和尽量大。请计算小爱获得的数字之和的最大值。
输入格式
- 单个整数表示 n
- n 个整数表示 a1,a2,…,an
输出格式
- 单个整数：表示先手小爱取走的最大数字之和。
数据范围
- 30%，1≤n≤20
- 60%，1≤n≤300
- 100%，1≤n≤5000
- 0≤ai≤40000
样例数据
输入:
5
10 20 30 40 50
输出:
90
解析：使用动态规划，
定义dp[i][j]表示先手可以取得ij区间数字的最大和
则对于dp[i][j],先手可以取a[i]或者a[j]，取a[i]，后手可以获得dp[i+1][j],先手可以获得a[i]+i到j的和去掉后手获得的dp[i+1][j]，同理可以算出取a[j]的情况下，先手可以获得的收获，取两者最值，即为答案。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[5005][5005];//dp[i][j]表示先手可以取得ij区间数字的最大和
int a[5005];
int b[5005];//前缀和
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i]+b[i-1];//前缀和
}
//初始化只取一个的情况
for (int i=1;i<=n;i++){
dp[i][i]=a[i];
}
//i从大到小，j从小到大填充右上半个二维矩阵
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++){
//取先手取a[i],a[j]到a[i+1]的和(b[j]-b[i])，去掉后手的最优解dp[i+1][j]
//或者先手取a[j]，a[i]到a[j-1]的和(b[j-1]-b[i-1])，去掉后手最优解dp[i][j-1]
dp[i][j]=max(a[i]+(b[j]-b[i])-dp[i+1][j],a[j]+(b[j-1]-b[i-1])-dp[i][j-1]);
}
}
printf("%d",dp[1][n]);
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~