洛谷 P2113 看球泡妹子（DP）

传送门https://www.luogu.com.cn/problem/P2113

解题思路

可以设  表示前  场比赛看了  场，小红的满足度为  的最大精彩度。

然后可以枚举前面的一个比赛 ，可以得到转移方程：

但是，我们发现数组空间有一点小大，可以优化一下。

发现每一次转移都是 ，于是可以滚动数组优化空间。

然后，观察数据范围 ，于是  的上限是 。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,c;
int f[101][2001];
int a[101],b[101],p[101],q[101];
int ans;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k>>c;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	
	for(int i=1;i<=m;i++)
	{
		cin>>p[i]>>q[i];
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=min(i,k);j>=1;j--)
		{
			for(int l=20*m;l>=b[p[i]]+b[q[i]];l--)
			{
				if(f[j-1][l-b[p[i]]-b[q[i]]]>0||l-b[p[i]]-b[q[i]]==0)//每次转移要判断是否计算出了 f[j-1][l-b[p[i]]-b[q[i]]]，或者是第一次选 
				f[j][l]=max(f[j][l],f[j-1][l-b[p[i]]-b[q[i]]]+a[p[i]]*a[q[i]]);
			 } 
				
		}
	}
	ans=-1;
	for(int i=1;i<=k;i++)
	{
		for(int j=c;j<=20*m;j++)
		ans=max(ans,f[k][j]);
	}
	if(ans)
	cout<<ans;
	else
		cout<<-1;
}