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

HDU 1505 City Game

編輯:關於C++

 

分析:直接用最大字矩陣的公式做超時了。換個思路,這題跟上一題1506有關系,先以每層為底算出每個元素能到達的最大的高度,然後就跟1506一樣了。這裡求高度和求面積兩處地方用到了dp暫存數據。求高度用二重循環,然後每層為底求面積要二重循環加上外層就是三重循環,但是由於用了dp保存中間結果,所以這個三重循環不會超時。dp[j]表示當前層第j列能到達的最大的高度,狀態轉移:1.a[i][j]=='R'時,dp[j]=0;2.否則,若a[i-1][j]=='F',則dp[j]++(這裡用到了dp,保存了前面層的數據,所以直接+1即可);若a[i-1][j]=='R',則dp[j]=1,。每層求面積的算法見1506題解

代碼:

 

#include
using namespace std;
int t,m,n;
int mx,sum;
int l[1005],r[1005],dp[1005];
char a[1005][1005];
int max(int i,int j)
{
	return i>j?i:j;
}
void fir()//處理第一層 
{
	mx=0;
	for(int j=0;j0&&dp[i]<=dp[t-1]) t=l[t-1];
		l[i]=t;
	}
	for(int i=n-2;i>=0;i--){
		int t=i;
		while(t0&&dp[i]<=dp[t-1]) t=l[t-1];
			l[i]=t;
		}
		for(int i=n-2;i>=0;i--){
			int t=i;
			while(t>t;
	while(t--){
		cin>>m>>n;
		for(int i=0;i>a[i][j];
		DP();
		cout<

 

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