看球泡妹子
题目背景
2014年巴西世界杯开幕了，现在满城皆是世界杯，商家们利用它大赚一笔，小明和小红也借此机会增进感情。
题目描述
本届世界杯共有\(N\)支球队，\(M\)场比赛。男球迷小明喜欢看比赛，女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为\(A_i\)，在小红眼里的帅哥数量为\(B_i\)。
每场比赛有两个球队对抗，它们的编号分别是\(P_i\)和\(Q_i\)。小明认为一场比赛的精彩度等于两队实力的乘积，小红则认为是两队帅哥数量之和。
由于体力的限制，他们最多只能看\(K\)场比赛。当然，只要看比赛，两个人一定会一起看。小明作为男生，理应迁就一下女生，所以，请你写一个程序，求出小红看到比赛的精彩度总和不小于\(C\)的情况下，小明看到比赛的精彩度的最大总和。
输入输出格式
输入格式：
第1行，4个正整数\(N，M，K，C\)。
第2行，\(N\)个空格隔开的正整数\(A_i\)。
第3行，\(N\)个空格隔开的正整数\(B_i\)。
之后\(M\)行，每行两个正整数\(P_i\)，\(Q_i\)。
输出格式：
一行，一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求，输出\(-1\).
输入输出样例
输入样例#1：
4 3 2 5
2 2 1 3
1 1 1 2
1 2
2 3
3 4
输出样例#1：
7
说明
对于\(20\%\)数据，\(N,M,K<=5\)。
对于全部数据，\(N<=100,K<=M<=100,Ai,Bi<=10,C<=1000\).
题解
其实是一道很简单的背包，调了半天（出负下标了）。
我们可以设\(dp[i][j][k]\)表示前\(i\)场比赛看了\(j\)场对于小红的精彩度为\(k\)时小明的最大精彩度。
下面就是类似背包的转移
不看这场比赛\(dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])\)
观看这场比赛\(dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-(b[p[i]]+b[q[i]])]+a[p[i]]*a[q[i]])\)
code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
#define N 105
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
int n,m,K,c,a[N],b[N],p[N],q[N];
int dp[N][N][1005],ans=-1,all;//先把ans=-1，并且初始化dp数组小于-1，最后无解直接输出-1。
int main(){
read(n);read(m);read(K);read(c);
for(R int i=1;i<=n;i++)read(a[i]);
for(R int i=1;i<=n;i++)read(b[i]);
for(R int i=1;i<=m;i++)read(p[i]),read(q[i]),all+=b[p[i]]+b[q[i]];
memset(dp,0xc0,sizeof(dp));
dp[0][0][0]=0;//下面就是裸的背包
for(R int i=1;i<=m;i++){
for(R int j=0;j<=K;j++){
for(R int k=all;k>=0;k--){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
if(k-(b[p[i]]+b[q[i]])>=0&&j>=1)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-(b[p[i]]+b[q[i]])]+a[p[i]]*a[q[i]]);//一定要判j>=1，否则会出现负下标。
}
}
}
for(R int i=0;i<=K;i++)
for(R int j=c;j<=all;j++)
ans=max(ans,dp[m][K][j]);
printf("%d\n",ans);
return 0;
}
