Link

ICPC2022Hangzhou C No Bug No Game

Question

给定 \(n\) 个物品和上限 \(k\)，要求最大化分数，物品的选择顺序可以任意

第 \(i\) 个物品一行 \(p_i\) 代表个数，后面 \(p_i\) 个 \(w_j\) 代表容量，定义 \(sum=\sum\limits_{j=1}^{i-1}\) ，对于第 \(i\) 个物品

• \(sum+p_i \le k\) 得到 \(w_{i,p_i}\) 的分
• \(sum>k\) 不得分呢
• 否则得到 \(w_{i,k-sum}\) 的分

Solution

可以看成是背包问题的变形，\(sum\) 为背包的容量，第一种情况就是全部塞进去，第二种情况就是塞不进去，第三种情况就是塞了半个东西进去

定义 \(F[i][j][0/1]\) 表示从前 \(i\) 个物品中选，总和为 \(j\) ，\(0\) 表示没有塞半个东西进去，\(1\) 表示已经塞了半个东西进去

转移就是背包的正常转移，需要注意第三维只能从 \(0->1\)

答案就是 \(\max (F[N][j][0/1])\ (j\le k)\)

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=3005;
int N,K;
int F[maxn][maxn][2],w[15];
inline int read(){
	int ret=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

int main(){
    N=read();K=read();
    
    memset(F,-0x3f,sizeof F);
    F[0][0][0]=0;
    for(int i=1;i<=N;i++){
        int p=read();
        for(int j=1;j<=p;j++) w[j]=read();
        for(int j=K-1;j>=0;j--){
            F[i][j][0]=F[i-1][j][0];F[i][j][1]=F[i-1][j][1];
            if(j+p<=K){ 
                F[i][j+p][0]=max(F[i][j+p][0],F[i-1][j][0]+w[p]);
                F[i][j+p][1]=max(F[i][j+p][1],F[i-1][j][1]+w[p]);
            }
            for(int now_k=1;now_k<p;now_k++){
                if(j+now_k<=K){
                    F[i][j+now_k][1]=max(F[i][j+now_k][1],F[i-1][j][0]+w[now_k]);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=N;i++)
    for(int j=0;j<=K;j++){
        ans=max(ans,F[i][j][0]);
        if(j==K) ans=max(ans,F[i][j][1]);
    }
    printf("%d\n",ans);
    return 0;
}