2022蓝桥杯国赛B组-费用报销-(线性dp|状态dp)

F

题意：
就是给你n张票据，每个票据有个时间和价格，你可以选择一些，使得这些票据的日期任意两个差要>=k，然后让总价值最接近m，但是不能超过m。

思考：
当时比赛的时候我就定义的用到i这个票据最多能表示的数是多少。这样有个弊端，这样可以保证最大，但是可能会超过m，超过m的只能特判，所以这样不能保证最接近m。所以当这样感觉不太合适的时候，可以把总价值成为dp的状态，也就是枚举到i点的时候，为j状态是否可达。然后转移就行了。但是这样的复杂度是nnm,将近1e9。所以会超时，但是可以得大部分分。所以可以进行优化，优化的点就是这个日期只有365天，所以dp[i][j]为到第i天j状态是否可达。然后对于物品的枚举可以用个变量cnt来一直往后走，这样复杂度是n*m+365的。因为每个点只会走一次所以只会循环n次m。这样复杂度就够了。

代码：

经典的线性dp

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define PII pair<int,int >
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 1005;

int T,n,m,k;
PII va[N];
int res[N],sum[N];
int dp[1010][5010];

signed main()
{
    
	IOS;
	cin>>n>>m>>k;
	res[1] = 31,res[2] = 28,res[3] = 31,res[4] = 30;
	res[5] = 31,res[6] = 30,res[7] = 31,res[8] = 31;
	res[9] = 30,res[10] = 31,res[11] = 30,res[12] = 31;
	for(int i=1;i<=12;i++) sum[i] = sum[i-1]+res[i];
	for(int i=1;i<=n;i++)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		int now = sum[a-1]+b;
		va[i] = {
    now,c};
	}
	sort(va+1,va+1+n);
	int cnt = 1;
	dp[0][0] = 1;va[0].fi = -100;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=0;j<=m;j++) dp[i][j] |= dp[i-1][j];
		for(int j=0;j<i;j++)
		{
    
			for(int t=va[i].se;t<=m;t++)
			{
    
				if(va[i].fi-va[j].fi>=k)
				dp[i][t] |= dp[j][t-va[i].se];
			}
		}
	}
	int maxn = 0;
	for(int i=m;i>=0;i--)
	{
    
		if(dp[n][i])
		maxn = max(maxn,i);
	}
	cout<<maxn;
	return 0;
}

优化后转化为状态dp
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define PII pair<int,int >
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const int N = 1005;

int T,n,m,k;
PII va[N];
int res[N],sum[N];
int dp[1010][5010];

signed main()
{
    
	IOS;
	cin>>n>>m>>k;
	res[1] = 31,res[2] = 28,res[3] = 31,res[4] = 30;
	res[5] = 31,res[6] = 30,res[7] = 31,res[8] = 31;
	res[9] = 30,res[10] = 31,res[11] = 30,res[12] = 31;
	for(int i=1;i<=12;i++) sum[i] = sum[i-1]+res[i];
	for(int i=1;i<=n;i++)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		int now = sum[a-1]+b;
		va[i] = {
    now,c};
	}
	sort(va+1,va+1+n);
	int cnt = 1;
	dp[0][0] = 1;
	for(int i=1;i<=365;i++)
	{
    
		for(int j=0;j<=m;j++) dp[i][j] |= dp[i-1][j];
		while(cnt<=n&&va[cnt].fi==i)
		{
    
			for(int j=0;j<=m;j++)
			{
    
				if(i>=k&&j>=va[cnt].se) dp[i][j] |= dp[i-k][j-va[cnt].se];
				else if(i<k&&j==va[cnt].se) dp[i][j] |= 1;
			}
			cnt++;
		}
	}
	int maxn = 0;
	for(int i=m;i>=0;i--)
	{
    
		if(dp[365][i])
		maxn = max(maxn,i);
	}
	cout<<maxn;
	return 0;
}

总结：
多多思考哈，多想一想类似可以解决的方法和优化。