AT_abc364_e 题解

ikunTLE · 2024-07-30 22:45:38 · 题解

题目传送门

思路

这是一道背包问题。定义 f_{i,j,k} 为前 i 道菜中吃 j 道且甜度为 k 时咸度的最小值。

状态转移方程：f_{i,j,k}\gets\min(f_{i-1,j,k},f_{i-1,j-1,k-a_i}+b_i)。

答案统计：设 x 为最大的 f_{N,j,k}\le Y 中的 j，答案即为 \min(x+1,N)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=100,M=1e4+10;
int a[N],b[N],f[N][N][M];
int main(){
    int n=read(),x=read(),y=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),b[i]=read();
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=n;++i)
        f[i][0][0]=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            for(int k=0;k<=x;++k){
                if(k>=a[i])
                    f[i][j][k]=f[i-1][j-1][k-a[i]]+b[i];
                f[i][j][k]=min(f[i][j][k],f[i-1][j][k]);
            }
    for(int i=n;i>=0;--i)
        for(int j=0;j<=x;++j)
            if(f[n][i][j]<=y)
                return printf("%d\n",min(i+1,n)),0;
    return 0;
}