工作

Description

这次故事的主角是HG！转眼4年过去了，HG本科毕业了，于是找了份工作。每天HG会收到一份任务清单，清单上列出了n个可能需要他完成的任务。每个任务包含3个信息：Ti、Ai、Bi，Ti表示完成此任务需要的时间，Ai表示此任务的到达时间，Bi表示此任务的最晚完成时间。在某一时刻若HG手上没有任务，那么他可以选择一个已经到达且还能够在Bi时刻之前（或者恰好在Bi时刻）完成的任务来做。
　　由于HG有点懒（纯属虚构:D），他想尽量少的减少他的总工作时间，但是他不能在可以做任务的时候故意不做（这样会被炒鱿鱼的>_<），那么他该如何挑选任务来做呢？
你的任务就是求出HG的最少工作时间（即总共有多少时间HG在做任务）。

Input

第一行一个整数n表示任务数。
以下n行，每行三个整数Ti,Ai,Bi。（n<=1000，0<=Ai,Bi<=1500，Ti>=1）

Output

输出仅一个数，即最少工作时间。

Sample Input

3
15 0 25
50 0 90
45 15 70
Sample Output

50
Hint

Ti>=1，0<=Ai,Bi<=1200；
30%的数据满足n<=5；60％的数据满足n<=500；100％的数据满足n<=1000。
输入数据保证Bi-Ai要大于等于Ti，且小于2Ti。

.
.
.
.
.
分析
DP
f[i]表示从开始时刻工作到第i时刻初（或者说是第i-1时刻末），当前空闲，目前最少工作时间是多少。
然后用f[i]去更新后面的时间点就行了。
接下来就可以推出动态规划方程：f[i+t[j]]:=min(f[i]+t[j],f[i+t[j]])但注意！由样例中，我们可以知道，HG做了第二项工作后就无法做完第三项！所以我们需要判断当前时间做此任务做不做得完(当然也要判断这个任务开启没有)
最后，当他i时刻为空闲时，我们可以用i时刻的工作时间去更新i+1时刻的工作时间

.
.
.
.
.
正解：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int f[2000],t[2000],a[2000],b[2000];

int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	int s=2147483647,e=-2147483647,n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t[i],&a[i],&b[i]);
		s=min(s,a[i]);
		e=max(e,b[i]);
	}
	for (int i=s;i<=e;i++)
		f[i]=2147483647;
	f[s]=0;
	for (int i=s;i<=e;i++)
		if (f[i]!=2147483647)
		{
			bool bz=true;
			for (int j=1;j<=n;j++)
				if (a[j]<=i&&i+t[j]<=b[j])
				{
					bz=false;
					f[i+t[j]]=min(f[i]+t[j],f[i+t[j]]);
				}
			if (bz==true) f[i+1]=min(f[i],f[i+1]);
		}
	printf("%d",f[e]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

.
.
.
.
暴力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int n,ans,now,nowmax;

struct edge
{
	int t,a,b;
} f[1010];


bool cmp(edge x,edge y)
{
	return x.a<y.a;
}

void dfs(int dep)
{
	if (now>=ans) return;
	if (dep==n+1)
	{
		ans=now;
		return;
	}
	if (nowmax+f[dep].t<=f[dep].b)
	{
		int w=nowmax;
		nowmax=max(f[dep].a,nowmax)+f[dep].t;
		now+=f[dep].t;
		dfs(dep+1);
		nowmax=w;
		now-=f[dep].t;
		if (dep<n&&f[dep].a==f[dep+1].a) dfs(dep+1);
	} else dfs(dep+1);
}

int main() 
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%d",&f[i].t,&f[i].a,&f[i].b);
	ans=2147483647;
	now=0;
	nowmax=-1;
	
	sort(f+1,f+n+1,cmp);
	dfs(1);
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}