题解 P2113 【看球泡妹子】
题目
看来各位的转移方程都是三维的，我这里有二维的
首先三维的楼上都说的挺清楚的，我就不再赘述
我们其实可以，类比01背包压缩空间（很明显，一场比赛不会为你打两次）
我们设f[x][y]为进行了y次，使女的满意值为x的男的最大满意值
类比01背包，我们可以认为这是个二维01背包，因此，容易得出：
f[x][y]=max(f[x][y],f[x-v[i]][y-1]+w[i])
其中，v[i],w[i]分别为女男的满意度（可以通过v[i]=b[p[i]]+b[q[i]] , w[i]=a[p[i]]*a[q[i]]得到）
由于十分明显，女的一开始对男的满意度为0，所以我们只能从0开始推
即把f的值都附为 -inf ，然后使f[0][y]=0即可
所以dp如下：
memset(f,143,sizeof(f));
memset(f[0],0,sizeof(f[0]));
for(int i=1;i<=m;i++)
for(int j=s;j>=v[i];j--)
for(int x=1;x<=k;x++)
f[j][x]=max(f[j][x],f[j-v[i]][x-1]+w[i]);
for(int i=c;i<=s;i++) ans=max(ans,f[i][k]);同时，有一个新问题：s是多少？
其他题解一般是开m的20倍，那大概是因为再大就mle了，所以其实他们的解法其实上有一定问题，只不过数据比较水，只要把k，c加到20多，他们题解就gg了，所以按最严格的的来说：
我们必须压到二维，而s为前k个最大的vi
所以AC代码如下：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,c,s,a[111],b[111],p[111],q[111];
ll v[111],w[111],v1[111],f[100001][101],ans=-1e9;//f[x][y]:进行y次，使女的满意值为x
int main()
{
memset(f,143,sizeof(f));
memset(f[0],0,sizeof(f[0]));
cin>>n>>m>>k>>c;
for(int i=1;i<=n;i++) scanf("%lld",a+i);
for(int i=1;i<=n;i++) scanf("%lld",b+i);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p[i],&q[i]);
w[i]=a[p[i]]*a[q[i]];
v1[i]=v[i]=b[p[i]]+b[q[i]];
}
sort(v1+1,v1+1+m);
for(int i=m;i>=m-k+1;i--) s+=v1[i];
for(int i=1;i<=m;i++)
for(int j=s;j>=v[i];j--)
for(int x=1;x<=k;x++)
f[j][x]=max(f[j][x],f[j-v[i]][x-1]+w[i]);
for(int i=c;i<=s;i++) ans=max(ans,f[i][k]);
if(ans<0) puts("-1");
else cout<<ans;
return 0;
}