hdu4833 Best Financing(dp)

hdu4833

题目

中文题目

思路

还是很菜啊，首先点很多所以要离散化，其次还是思路上的问题吧，获得的每一笔钱之间是互相没有关系的，我们只要考虑把它进行哪几次投资以获得最大的rate，然后加起来就行了，对于最大的rate，将时间连成一张有向图，根据时间序以及产品给的起止时间，然后就类似数塔进行dp即可。

代码

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<stack> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int maxn=25100; int d[maxn],e[maxn],s[maxn],f[maxn],r[maxn]; int point[maxn*4]; int tot,num; int dp[maxn*4]; int head[maxn*4]; struct node { int next; int to; int w; } edge[maxn]; void addedge(int from,int to,int w) { edge[tot].to=to; edge[tot].next=head[from]; edge[tot].w=w; head[from]=tot++; } int getnum(int x) { return lower_bound(point,point+num,x)-point; } void solve(int n) { memset(dp,0,sizeof(dp)); for(int i=n-1; i>=0; i--) { for(int j=head[i]; ~j; j=edge[j].next) { int v=edge[j].to; int w=edge[j].w; dp[i]=max(dp[i],dp[v]+w); } } } int main() { int T; scanf("%d",&T); int kase=1; while(T--) { memset(head,-1,sizeof(head)); tot=0; int n,m; scanf("%d %d",&n,&m); for(int i=0; i<n; i++) { scanf("%d %d",&d[i],&e[i]); point[tot++]=d[i]; } for(int i=0; i<m; i++) { scanf("%d %d %d",&s[i],&f[i],&r[i]); point[tot++]=s[i],point[tot++]=f[i]; } sort(point,point+tot); num=unique(point,point+tot)-point; tot=0; for(int i=1; i<num; i++) addedge(i-1,i,0); for(int i=0; i<m; i++) { int a=getnum(s[i]); int b=getnum(f[i]); addedge(a,b,r[i]); } solve(num); ll ans=0; for(int i=0; i<n; i++) { ans+=(ll)e[i]*dp[getnum(d[i])]; } printf("Case #%d:\n",kase++); printf("%I64d.%02d\n",ans/100,ans%100); } return 0; }