手机网站开发模拟,公司备案证查询网站查询,排名前十的招聘app,天津武清做淘宝网站正题
题目链接:https://www.luogu.com.cn/problem/P3507 题目大意 nnn个数#xff0c;没人轮流取若干个并获得取走的数中最小数的权值#xff0c;两人的目标都是自己的权值−-−对方的权值最大#xff0c;求先手的权值−-−后手的权值。 解题思路
肯定是从大往小取#x…正题
题目链接:https://www.luogu.com.cn/problem/P3507 题目大意
nnn个数没人轮流取若干个并获得取走的数中最小数的权值两人的目标都是自己的权值−-−对方的权值最大求先手的权值−-−后手的权值。 解题思路
肯定是从大往小取所以我们从小往大dpdpdp。 设fi,0/1f_{i,0/1}fi,0/1表示取了前iii个最后一步是先/后手。
然后有fi,0max{fj,1aj1}(ji),fi,1min{fj,0−aj1}(ji)f_{i,0}max\{f_{j,1}a_{j1}\}(ji),f_{i,1}min\{f_{j,0}-a_{j1}\}(ji)fi,0max{fj,1aj1}(ji),fi,1min{fj,0−aj1}(ji)
记录一下最大值转移即可时间复杂度O(n)O(n)O(n)。
可以每次权值取反省去第二维。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610;
ll n,a[N],f[N][2];
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);sort(a1,a1n);for(ll i1,maxs0,mins0;in;i){minsmin(mins,f[i-1][0]-a[i]);maxsmax(maxs,f[i-1][1]a[i]);f[i][0]maxs;f[i][1]mins;}printf(%lld\n,f[n][0]);
}
