$$\mathrm{看球泡妹子}$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{P}2113$

题目背景

2014 年巴西世界杯开幕了，现在满城皆是世界杯，商家们利用它大赚一笔，小明和小红也借此机会增进感情。

题目

本届世界杯共有 $n$ 支球队，$m$ 场比赛。男球迷小明喜欢看比赛，女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为 $a_i$，在小红眼里的帅哥数量为 $b_i$。

每场比赛有两个球队对抗，它们的编号分别是 $p_i$ 和 $q_i$。小明认为一场比赛的精彩度等于两队实力的乘积，小红则认为是两队帅哥数量之和。

由于体力的限制，他们最多只能看 $k$ 场比赛。当然，只要看比赛，两个人一定会一起看。小明作为男生，理应迁就一下女生，所以，请你写一个程序，求出小红看到比赛的精彩度总和不小于 $c$ 的情况下，小明看到比赛的精彩度的最大总和。

输入

第一行包含四个正整数 $n,m,k,c$。

第二行有 $n$ 个用空格隔开的正整数 $a_i$。

第三行有 $n$ 个用空格隔开的正整数 $b_i$。

接下来 $m$ 行，每行两个正整数 $p_i,q_i$。

输出

一行，一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求，输出 -1。

样例输入

4 3 2 5
2 2 1 3
1 1 1 2
1 2
2 3
3 4

样例输出

7

数据范围

• 对于 $20\%$ 数据，$1\le n,m,k\le 5$。
• 对于 $100\%$ 数据，$1\le n\le 100$，$1\le k\le m\le 100$，$1\le a_i,b_i\le 10$，$1\le c\le 10^3$。

思路

这道题是 dp 。

就 $f_{i,j,k}$ 表示前 $i$ 场比赛看 $j$ 场，女生的精彩程度是 $k$ 时，男生最多有多少精彩程度。
初始化就是 $f_{i,0,0}$ 的值为 $0$ 。（$0\le i\le m$）
那也很好转移，就是从 $f_{i-1,j-1,k-gir{l}_i}$ 过来。
（当然 $k-gir{l}_i$ 要是正整数，$gir{l}_i$ 就是第 $i$ 场比赛对女生精彩程度的贡献度）

最后就输出 $f_{m,k}$ 里面第三维大于等于 $c$ 的。

代码

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int n, m, c, K, a[101], b[101], x, y, boy[101], girl[101], f[101][101][2501], ans = -1, sum;

int main() {
	memset(f, -0x7f, sizeof(f));//初始化
	
	scanf("%d %d %d %d", &n, &m, &K, &c);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		boy[i] = a[x] * a[y];//这一场比赛对两个精彩程度的贡献
		girl[i] = b[x] + b[y];
		sum += girl[i];//求出女生最多有多少精彩程度
	}
	
	for (int i = 0; i <= m; i++) f[i][0][0] = 0;//初始化
	
	for (int i = 1; i <= m; i++)//dp
		for (int k = 1; k <= i; k++)
			for (int j = 0; j <= sum; j++)
				if (j >= girl[i]) f[i][k][j] = max(f[i - 1][k][j], f[i - 1][k - 1][j - girl[i]] + boy[i]);
					else f[i][k][j] = f[i - 1][k][j];
	
	for (int i = c; i <= sum; i++)//找到最大值
		ans = max(ans, f[m][K][i]);
	
	printf("%d", ans);
	
	return 0;
}