费用报销（01背包

本文主要是介绍费用报销（01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int n,m,k;
struct node {int m,d,v;
}a[1007];
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dp[1007][2],mm[13],mx;
map<int,int> mp;
int main(){ios;for(int i=1;i<=12;i++)mm[i]=mm[i-1]+mon[i];cin>>n>>m>>k;for(int i=0;i<n;i++)cin>>a[i].m>>a[i].d>>a[i].v;for(int i=0;i<n;i++){int dd=mm[a[i].m-1]+a[i].d;mx=max(mx,dd);mp[dd]=max(mp[dd],a[i].v);}for(int i=1;i<=mx;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]);if(i-k<=0)dp[i][1]=mp[i];if(i-k>0)dp[i][1]=mp[i]+max(dp[i-k][1],dp[i-k+1][0]);
//		cout<<max(dp[i][0],dp[i][1])<<'\n';}cout<<max(dp[mx][0],dp[mx][1]);return 0;
}

这篇关于费用报销（01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---