2022 Blue Bridge Cup group B - expense reimbursement - (linear dp| status DP)

F

The question ：
It's for you. n Bills , Each note has a time and price , You can choose some , Make the difference between any two dates of these bills >=k, Then make the total value closest to m, But not more than m.

reflection ：
At that time, I used the definition of i What is the maximum number that this note can represent . There is a drawback to this , This will ensure maximum , But it may exceed m, exceed m Only special judgment , So this does not guarantee the closest m. So when it doesn't feel right , You can turn the total value into dp The state of , That is, enumerate to i A.m. , by j Whether the status can reach . And then transfer it . But the complexity is nnm, nearly 1e9. So it will time out , But you can get most of the points . So it can be optimized , The optimization point is that this date only has 365 God , therefore dp[i][j] For the first time i God j Whether the status can reach . Then for the enumeration of items, you can use a variable cnt Come and go straight back , The complexity is n*m+365 Of . Because each point only goes once, it only circulates n Time m. This complexity is enough .

Code ：

 Classical linear 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;
}

 Convert to status after optimization 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;
}

summary ：
Think more , Think about similar solutions and optimizations .