洛谷-P1280 尼克的任務

題目描述

尼克每天上班之前都連接配接上英特網，接收他的上司發來的郵件，這些郵件包含了尼克主管的部門當天要完成的全部任務，每個任務由一個開始時刻與一個持續時間構成。

尼克的一個工作日為N分鐘，從第一分鐘開始到第N分鐘結束。當尼克到達機關後他就開始幹活。如果在同一時刻有多個任務需要完成，尼克可以任選其中的一個來做，而其餘的則由他的同僚完成，反之如果隻有一個任務，則該任務必需由尼克去完成，假如某些任務開始時刻尼克正在工作，則這些任務也由尼克的同僚完成。如果某任務于第P分鐘開始，持續時間為T分鐘，則該任務将在第P+T-1分鐘結束。

寫一個程式計算尼克應該如何選取任務，才能獲得最大的空暇時間。

輸入輸出格式

輸入格式：

輸入資料第一行含兩個用空格隔開的整數N和K(1≤N≤10000，1≤K≤10000)，N表示尼克的工作時間，機關為分鐘，K表示任務總數。

接下來共有K行，每一行有兩個用空格隔開的整數P和T，表示該任務從第P分鐘開始，持續時間為T分鐘，其中1≤P≤N，1≤P+T-1≤N。

輸出格式：

輸出檔案僅一行，包含一個整數，表示尼克可能獲得的最大空暇時間。

輸入輸出樣例

輸入樣例#1： 

15 6
1 2
1 6
4 11
8 5
8 1
11 5
      

輸出樣例#1： 

4      

老實說  做這一道題沒看題解之前我是一臉懵逼的... 這個怎麼玩?狀态轉移方程怎麼搞?要不遞推改搜尋???

直到看到題解區大佬提了一下... 要逆着推, 然後恍然大悟原來還可以這樣子搞...妙啊!!!算法真是太妙了,dp真是太妙了,是以我還是想說  I hate DP.

這道題目思維搞清楚了就沒有任何難度了, 以時間點逆着推, dp[i]表示i到n之間的最大空閑時間

如果i時間點沒有任務的話 dp[i] = dp[i+1]+1;//等于上一個時間點的最大空閑時間+1

如果i時間點有任務的話, 我們就周遊所有的任務, 求出最大的空閑時間為多少

即dp[i] = max(dp[i] , dp[i+time[j]] );//time[j]表示i時間點的那個任務的結束時間

這個地方有一個問題就是怎麼快速的找到i時間開始的任務

如果用臨街舉證 time[i][j]表示i時刻持續時間為j的話,這樣空間消費太大

我用的是

vector<int> vec[n];//vec[i]表示i時刻開始,如果vec[i].empty() ,表示i時間點沒有

要周遊i時間點的所有任務也很簡單

for(int j=0;j<vec[i].size();j++) 這樣就行了

下面貼上本題代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> 
using namespace std;
int n,k;
int dp[10005];
vector<int> vec[10005];
int main(){
	int a,b;
	memset(dp,0,sizeof(dp));
	cin>>n>>k;
	for(int i=0;i<k;i++){
		cin>>a>>b;
		vec[a].push_back(b);
	}
	
	for(int i=n;i>=1;i--){
		if(vec[i].size()){//這個時間點有任務
			int ans = 0;
			for(int j=0;j<vec[i].size();j++)
				ans = max(ans,dp[i+vec[i][j]]);
			dp[i] = max(ans,dp[i]);
		}else{
			dp[i] = dp[i+1]+1;
		}
	}
	
	cout<<dp[1]<<endl;
	return 0;
}