题目:http://acm.hdu.edu.cn/showproblem.php?pid=4502
思路:一个简单的dp ,比赛时没做出来呢。。。。。
d[i]代表 到第i天时的最大值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int main()
{
int p[110][110],d[110];
int t,i,j,m,n,s,e,c;
cin>>t;
while(t--)
{
memset(p,0,sizeof(p));
memset(d,0,sizeof(d));
cin>>m>>n;
for(i=1; i<=n; i++)
{
scanf("%d%d%d",&s,&e,&c);//用cin 好像会超时
if(p[s][e]<c)
p[s][e]=c;
}
for(i=1; i<=m; i++)
for(j=0; j<=i; j++)
{
d[i]=max(d[i],d[j]+p[j+1][i]);//比较好的设计。
}
cout<<d[m]<<endl;
}
return 0;
}
上面的代码 写的思路挺清晰的,d 和 e数组都是 按照 天来的。
下面 贴一下我的代码 ,思路混乱,而且错了。。。d 是按天来的,但是不是按照天算的。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; int main()
{
int t,i,j,m,n,s[1100],e[1100],c[1100];
int d[1100],max;
cin>>t;
while(t--)
{
memset(d,0,sizeof(d));
cin>>m>>n;
j=1;
for(i=1; i<=n; i++)
{
scanf("%d%d%d",&s[j],&e[j],&c[j]);
if(s[j]<=m&&e[j]<=m&&s[j]>=1&&e[j]>=1)
{
if(c[j]>d[e[j]])
d[e[j]]=c[j];
j++;
}
else continue;
}
if(s[j]<=m&&e[j]<=m&&s[j]>=1&&e[j]>=1)
n=j;
else
n=j-1;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
if(s[j]>e[i]&&d[e[j]]<d[e[i]]+c[j])
d[e[j]]=d[e[i]]+c[j];
}
max=-1;
for(i=1; i<=m; i++)
if(d[i]>max)
max=d[i];
cout<<max<<endl;
}
return 0;
}