![【线性DP】P10156 [LSOT-2] 胜者组](http://pic.xiahunao.cn/yaotu/【线性DP】P10156 [LSOT-2] 胜者组)
解题思路开一个结构体存储学生的序号、a值和c值。对输入的数据先按c值排序c值相同情况下按序号排序。定义dp数组dp[i][j]表示排序后的前i个人里选了j人的最小满意度。初始化memset(dp,0x3f,sizeof(dp));for(int i0;in;i)dp[i][0]0;如果j是奇数一种情况是如果前一个人和他同一个团体不选第i个人可以使dp[i][j]dp[i-1][j]还有一种考虑选第i个人dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].a-xs[i].idx)。s[i].a-xs[i].idx我们可以这样考虑最终t出去的人是偶数现在j是奇数所以根据不满意的计算a[i]a[j]x*|i-j|后面会有一个数和j配对这里就把j对应的序号s[i].idx减去。如果j是偶数一种情况是选第i个且上一个人和第i个人同组就可以得出dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].ax*s[i].idx)。还有一种情况是不选第i个人则dp[i][j]min(dp[i][j],dp[i-1][j])。AC Code#includebits/stdc.husingnamespacestd;#definelllonglongll n,m,k,x,dp[5005][5005];structstu{inta,c,idx;friendbooloperator(stu p,stu q){if(p.c!q.c)returnp.cq.c;returnp.idxq.idx;}}s[5005];intmain(){cinnmkx;mn-m;if(m%2)m;for(inti1;in;i){s[i].idxi;cins[i].a;}memset(dp,0x3f,sizeof(dp));for(inti0;in;i)dp[i][0]0;for(inti1;in;i)cins[i].c;sort(s1,sn1);for(inti1;in;i){for(intj1;jmin(i*1ll,m);j){if(j%2!0){if(s[i].cs[i-1].c)dp[i][j]dp[i-1][j];dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].a-x*s[i].idx);}else{dp[i][j]dp[i-1][j];if(s[i].cs[i-1].c)dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].ax*s[i].idx);}}}if(dp[n][m]1e18)coutdp[n][m];elsecoutImpossible;return0;}
解题思路开一个结构体存储学生的序号、a值和c值。对输入的数据先按c值排序c值相同情况下按序号排序。定义dp数组dp[i][j]表示排序后的前i个人里选了j人的最小满意度。初始化memset(dp,0x3f,sizeof(dp));for(int i0;in;i)dp[i][0]0;如果j是奇数一种情况是如果前一个人和他同一个团体不选第i个人可以使dp[i][j]dp[i-1][j]还有一种考虑选第i个人dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].a-xs[i].idx)。s[i].a-xs[i].idx我们可以这样考虑最终t出去的人是偶数现在j是奇数所以根据不满意的计算a[i]a[j]x*|i-j|后面会有一个数和j配对这里就把j对应的序号s[i].idx减去。如果j是偶数一种情况是选第i个且上一个人和第i个人同组就可以得出dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].ax*s[i].idx)。还有一种情况是不选第i个人则dp[i][j]min(dp[i][j],dp[i-1][j])。AC Code#includebits/stdc.husingnamespacestd;#definelllonglongll n,m,k,x,dp[5005][5005];structstu{inta,c,idx;friendbooloperator(stu p,stu q){if(p.c!q.c)returnp.cq.c;returnp.idxq.idx;}}s[5005];intmain(){cinnmkx;mn-m;if(m%2)m;for(inti1;in;i){s[i].idxi;cins[i].a;}memset(dp,0x3f,sizeof(dp));for(inti0;in;i)dp[i][0]0;for(inti1;in;i)cins[i].c;sort(s1,sn1);for(inti1;in;i){for(intj1;jmin(i*1ll,m);j){if(j%2!0){if(s[i].cs[i-1].c)dp[i][j]dp[i-1][j];dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].a-x*s[i].idx);}else{dp[i][j]dp[i-1][j];if(s[i].cs[i-1].c)dp[i][j]min(dp[i][j],dp[i-1][j-1]s[i].ax*s[i].idx);}}}if(dp[n][m]1e18)coutdp[n][m];elsecoutImpossible;return0;}
