Miku

悬线法：

对于每一个点，我们以这个点为矩形的最低点，然后向左右检查最大扩展位置，然后向上找在此情况下的最大高度

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 205;
const int V = 5005;
const int K = 55;
int n,k,v;
int vi[N],wi[N];
int f[2][V][K];
int x[2*K];
bool cmp(int x,int y)
{
    return (x>y);
}
int main()
{
    int i,j,l;
    scanf("%d%d%d",&k,&v,&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&vi[i],&wi[i]);
    memset(f,0xc0,sizeof f);
    f[0][0][1]=0;
    for(i=1;i<=n;++i)
    {
        for(j=0;j<=v;++j)
        {
            if(j<vi[i])
            {
                for(l=1;l<=k;++l)
                    f[i%2][j][l]=f[(i-1)%2][j][l];
            }
            else
            {
                for(l=1;l<=k;++l)
                    x[l]=f[(i-1)%2][j][l];
                for(l=1;l<=k;++l)
                    x[l+k]=f[(i-1)%2][j-vi[i]][l]+wi[i];
                sort(x+1,x+2*k+1,cmp);
                for(l=1;l<=k;++l)
                f[i%2][j][l]=x[l];
            }
        }
    }
    int ans=0;
    for(l=1;l<=k;++l)
        ans+=f[n%2][v][l];
    printf("%dn",ans);
    return 0;
}