TV Battle --HOJ 11915

1、题目类型：DP。

2、解题思路：（1）对输入TV Battle 按其终点进行排序；（2）DP时间点1--10080每个时间点的最大收益值，dp[i]表示第 i 个时间点的最大收益值。

3、注意事项：注意按照终点排序，开始点不行。

3、实现方法:

#include<iostream>
#include<algorithm>
using namespace std;
const int M=10085;
const int N=100005;

struct Node
{
int b,l,v;
};
Node Arr[N];
int n,dp[M];

bool cmp(Node p1,Node p2)
{
return p1.b+p1.l<p2.b+p2.l;
}

void DP()
{
int i,j=0,tmp;
memset(dp,0,sizeof(dp));
for(i=1;i<=M;i++)
{
tmp=Arr[j].b+Arr[j].l;
dp[i]=dp[i-1];
if(tmp>i)
{
continue;
}
while(tmp==i)
{
dp[i]=dp[i]>dp[i-Arr[j].l]+Arr[j].v ? dp[i] :dp[i-Arr[j].l]+Arr[j].v;
j++;
tmp=Arr[j].b+Arr[j].l;
}
}
}

int main()
{
int c,i;
cin>>c;
while(c--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d",&Arr[i].b,&Arr[i].l,&Arr[i].v);
sort(Arr,Arr+n,cmp);
DP();
cout<<dp[M]<<endl;
}
return 0;
}

 

转载于:https://www.cnblogs.com/yongze103/archive/2010/09/27/1837080.html

总结

以上是生活随笔为你收集整理的TV Battle --HOJ 11915的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。