luogu P2113 看球泡妹子

2333 这么水的蓝题

f[i][j] 表示看了i场比赛,小♀红的什么东西为j时小♂明的什么值强行压维蛤蛤

剩下的转移很简单(注意i的循环顺序从后往前,01背包)

(具体见代码)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

#include<cmath>

#define il inline

using namespace std;

const long long mod=1000000007;

int n,m,kk,c;

int a[110],b[110],f[110][1010];

int main()

{

    memset(f,-0x3f3f3f,sizeof(f));f[0][0]=0;

    scanf("%d%d%d%d",&n,&m,&kk,&c);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++) scanf("%d",&b[i]);

    while(m--)

    {

        int x,y,xx,yy;

        scanf("%d%d",&x,&y);

        xx=a[x]*a[y];yy=b[x]+b[y];

        for(int i=kk-1;i>=0;i--)

            for(int j=0;j<=c;j++)

                f[i+1][min(c,j+yy)]=max(f[i+1][min(c,j+yy)],f[i][j]+xx);

    }

    printf("%d\n",max(f[kk][c],-1));

    return 0;

}