程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4293 Groups（區間dp）

HDU 4293 Groups（區間dp）

編輯：C++入門知識

HDU 4293 Groups（區間dp）

HDU 4293

題意：有 n 個人，可任意分成若干組，然後每個人各提供一個信息，表示他們組前面有多少個人，後面有多少個人。問最多有多少個信息是真實的的。

思路：

這道題一開始給我的印象是什麼亂七八糟的東西，後來也沒想通到底該怎麼做，好在賽後百度在手天下我有：）

我們可以把這n個人看成一段區間 [1,n]。
設每個人的信息是a、b，則這個信息代表了他們組所在的區間 [a+1,n-b]。

若a+b>n,顯然撒謊，跳過不做處理。

我們用一個Map[i][j]數組將同在一區間[i,j]的人數紀錄下來，紀錄過程中若Map[i][j] > n-i-j則說明提供[i,j]區間消息的人裡有人撒謊，略過不計，令Map[i][j] = n-i-j；

問題轉化成了在 [1,n] 這段區間中分布的若干個帶有權值的區間，問如何選取一些不相交的區間，使權值之和最大。

我們用dp[i]表示[1,i]區間權值之和的最大值，轉移方程為dp[i] = max(dp[i],dp[j]+map[j][i]).

code:

/*
* @author Novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 2147483647
#define cls(x) memset(x,0,sizeof(x))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
using namespace std;
const double eps(1e-8);
typedef long long lint;

const int maxn = 500 + 5;

int Map[maxn][maxn];
int dp[maxn];

int main(){
//	freopen(input.txt,r,stdin);
	int n;
	while(cin >> n){
		cls(Map);
		for(int i = 1 ; i <= n ; i++){
			int a,b;
			scanf(%d%d,&a,&b);
			if(a+b >= n)
				continue;
			else{
				if(n-a-b > Map[a+1][n-b])
					Map[a+1][n-b]++;
				else 
					Map[a+1][n-b] = n-a-b;
			}
		}
		cls(dp);
		for(int i = 1 ; i <= n ; i++)
			for(int j = 1 ; j <= i ; j++)
				dp[i] = max(dp[i] , dp[j-1]+Map[j][i]);
		cout << dp[n] << endl;
	}
		
	return 0;
}