费用报销
01背包
思路:f[i][j]表示前i个票据在容量为j的背包中能占的最大值。
#include<iostream>
#include<algorithm>
using namespace std;
int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dp[1005][5005];
int s[13];
int last[1005];
struct node
{
int m,d,v,t;
}arr[1005];
bool cmp(node &n1,node &n2)
{
return n1.t<n2.t;
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
//s数组为了后面便于将每个日期转为一年365天某一天
for(int i=2;i<=12;i++) s[i]=s[i-1]+day[i-1];
for(int i=1;i<=n;i++)
{
cin>>arr[i].m>>arr[i].d>>arr[i].v;
arr[i].t=s[arr[i].m]+arr[i].d;
}
sort(arr+1,arr+n+1,cmp);
//找到前一个合法的日期
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
{
if(arr[i].t-arr[j].t>=k) last[i]=j;
}
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=arr[i].v;j--)
{
dp[i][j]=dp[i-1][j];
dp[i][j]=max(dp[i][j],dp[last[i]][j-arr[i].v]+arr[i].v);
}
}
cout<<dp[n][m]<<endl;
return 0;
}