程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4293 Groups(區間dp)

HDU 4293 Groups(區間dp)

編輯:關於C++

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;
}



 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved