费用报销

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