Java教程

P1280 尼克的任务(DP)

本文主要是介绍P1280 尼克的任务(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

注意要倒序。

 

设f[i]表示从第i时刻到第n时刻的最大休闲时间。

 

```cpp

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int N=10005;
int f[N];
int cnt[N];
vector<int> v[N]; 
int n,k;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++){
		int p,t;
		scanf("%d%d",&p,&t);
		v[p].push_back(t);
		cnt[p]++;
	}
	for(int i=n;i>=1;i--){
		if(cnt[i]){
			for(int j=0;j<cnt[i];j++){
				f[i]=max(f[i],f[i+v[i][j]]);
			}
		}
		else f[i]=f[i+1]+1;
	}
	printf("%d",f[1]);
	return 0;
}

```

这篇关于P1280 尼克的任务(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!