正题

题目链接:/problem/CF388C

题目大意

有nnn堆卡片，第iii堆有sis_isi​张，给出每张卡的权值。现在先手选择一堆取走堆底的牌，然后后手选择一堆取走堆顶的牌，直到所有牌被取走。在双方都要求最大化取走的牌的权值的情况下求先后手的权值。

1≤n,si≤100,1≤ai,j≤10001\leq n,s_i\leq 100,1\leq a_{i,j}\leq 10001≤n,si​≤100,1≤ai,j​≤1000

解题思路

大胆猜测结论是每堆牌都是先后手各自取走约一半的牌，因为如果总和固定最大化自己就相当于最小化对方。

如果存在一种情况后手和先手各自取不同的堆，那么这肯定是对后手优的，又因为权值一样，也就是对先手劣的，与对先手和后手都优冲突。

现在偶数个数的都是平分的，主要考虑奇数，对于奇数来说就是先手取走中间那个然后交换先后手。

直接把奇数两边的平分，然后拿中间出来排序，先后手依次取走即可。

时间复杂度：O(ns)O(ns)O(ns)

code

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=110;int n,s,sum,ans,m,a[N],r[N];int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&s);for(int j=1;j<=s;j++)scanf("%d",&a[j]),sum+=a[j];if(s&1){++m;for(int j=1;j<=s/2;j++)ans+=a[j];for(int j=s/2+2;j<=s;j++)ans-=a[j];r[m]=a[s/2+1];}else{for(int j=1;j<=s/2;j++)ans+=a[j];for(int j=s/2+1;j<=s;j++)ans-=a[j];}}sort(r+1,r+1+m);reverse(r+1,r+1+m);for(int i=1;i<=m;i++)if(i&1)ans+=r[i];else ans-=r[i];printf("%d %d\n",int(sum/2.0+ans/2.0),int(sum/2.0-ans/2.0));return 0;}