传送门点我
思路:
很明显的一道动态规划问题.根据题目我们可以考虑0-1背包
和0-1背包板子题相比，它只是多出了可以额外放一个的条件.
那么我们不难看出结论:在最优情况下，我们一定会选择价值最高的物品作为那额外1个的使用者。
那么我们不妨设价值最高的那个物品的重量为 0 ,然后写0-1背包的板子。最后的答案就是dp[n-1].
附上部分代码:
int mx=INT_MIN,mxid=0;
for(int i = 1;i<= m ;i ++){
输入t数组
}
for(int i=1;i<=m;i++){
输入v数组
取价值最大
}
t[价值最大值下标]=0;
for(int i=1;i<=m;i++){
for(int j=n-1;j>=t[i];j--){
/*0-1背包模板*/
}
}
cout <<f[n-1];
}