普普通通的动态规划

解题思路:先把月份和天数换算成一年第几天，然后从小到大排序。然后进行动态规划，dp[i][j]表示选到第i个为止时金额j是否能取到，last代表第i个之前的最近的距离i时间差大于等于k的序号。如果没有last就等于0。状态转移方程:dp[i][j] = dp[i - 1][j] | (j >= a[i].v ? dp[last][j - a[i].v] : 0)
注意事项:
每个序号转移之前可以先把的dp[i-1]复制过来。因为前一个的天数要小于等于这一个，所以到前一个的天数位置能取到的到这一个的天数肯定也能取到。
参考代码:

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define getl(s) getline(cin,s)
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b
#define abs(a)   a > 0 ? a : -a
#define lowbit(a) a & -a
using namespace std;
const int N = 1e3 + 5;
const int M = 5e3 + 5;
struct node 
{
	int day,v;
}a[N];
int n,m,k,dp[N][M];//dp[i][j]代表选择到第i个时金额j是否能取到 
int mon[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int getday(int m,int d)
{
	int res = 0;
	for(int i = 0;i < m;i++)
		res += mon[i];
	return res + d;
} 
bool cmp(node x,node y)
{
	return x.day < y.day;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i = 1;i <= n;i++)
	{
		dp[i][0] = 1;
		int m,d;cin>>m>>d>>a[i].v;
		a[i].day = getday(m,d);
	}
	//按照时间先后顺序排列 
	sort(a + 1,a + n + 1,cmp);
	for(int i = 1;i <= n;i++)
	{
		int last = i - 1;
		//找到最近的距离i超过k天的序号 
		while(a[i].day - k < a[last].day && last > 0)last--;
		for(int j = m;j >= 0;j--)
		{
			dp[i][j] = dp[i - 1][j];
			if(j >= a[i].v)dp[i][j] |= dp[last][j - a[i].v];
		}	
	}
	for(int i = m;i >= 0;i--)
		if(dp[n][i])
		{
			cout<<i;
			break;		
		}
	return 0;
}