Educational CF Round 87___F. Summoning Minions —— dp

本文主要是介绍Educational CF Round 87___F. Summoning Minions —— dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 张牌，最多放 $k$ 张，可以放了之后删掉
    每张牌初始战力为 $a_i$，上场后场上所有牌的战力增加 $b_i$
    输出使最终战力和最大的方案

解题思路：

    鉴于昨天 $dp$ 把 $i$ 写成 $cnt$ 找了三个小时，这道题又没想出来，所以还是写一下吧
    很明显先上 $k-1$ 张牌之后开始 $buff$ 最优，最后再上场一张牌即可
    因此按照 $b_i$ 排序之后就可直接选取了，因为 $b_i$ 大的肯定放在后面好
    看了一下别人的方法有各种各样的建图方法，仿佛欣赏名画一样
    设 $dp[i][j]$ 为到 $i$ 为止，选了 $j$ 张牌的最优值
    若选取这张牌作为 $buff$ 牌，则只考虑 $buff$
    若选取这张牌一直保留到最后，则要考虑 $a_i$ 和 $buff$
    然后记录一下路径即可

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 80;
int n, k, T, chos[maxn];
int dp[maxn][maxn], path[maxn][maxn];
struct node{int a, b, id;bool operator < (const node &A) {return b < A.b;}
} a[maxn];signed main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);for(int i=1; i<=n; i++) scanf("%d%d", &a[i].a, &a[i].b), a[i].id = i;sort(a+1, a+1+n);memset(dp, 128, sizeof(dp));memset(chos, 0, sizeof(chos));memset(path, 0, sizeof(path));dp[0][0] = 0;for(int i=1; i<=n; i++)for(int j=0; j<=min(i, k); j++){if(dp[i-1][j] >= 0){dp[i][j] = dp[i-1][j] + a[i].b * (k - 1);}if(j > 0 && dp[i-1][j-1] >= 0){if(dp[i][j] >= dp[i-1][j-1]+a[i].a+a[i].b*(j-1)) continue;dp[i][j] = dp[i-1][j-1] + a[i].a + a[i].b * (j - 1);path[i][j] = 1;}}for(int i=n, j=k; i; i--)if(path[i][j]) chos[a[i].id] = 1, j--;printf("%d\n", k + (n - k) * 2);int cnt = 0, last = 0;for(int i=1; i<=n; i++){if(!chos[a[i].id]) continue;if(++cnt == k){last = a[i].id;break;}printf("%d ", a[i].id);}for(int i=1; i<=n; i++){if(chos[a[i].id]) continue;printf("%d %d ", a[i].id, -a[i].id);}printf("%d\n", last);}
}

这篇关于Educational CF Round 87___F. Summoning Minions —— dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---