Ural 1102 1112 1119 1138 1146

本文正體字版由OpenCC轉換

==1102== 對於讀入的每一行分別進行動態規劃。

狀態 F[i]前i爲是否可以連續達到

狀態轉移方程 F[i]= or { F[i-Len[j] | i-Len[j]>=0 並且 S[i-Len[j]+1] 匹配 W[j] }

邊界條件 F[0]=true

目標結果 F[L]

==1112==

我們先對所有的區間的左端進行排序，然後進行動態規劃。設第0個區間座標爲(-1000,-1000)，第N+1個區間座標爲(1000,1000)。動態規劃中記錄下每個狀態的前驅狀態，用來輸出方案。

狀態 F[i] 前i的區間中，如果互不相交，留下的最大數量

狀態轉移方程

F[i] = Max{ F[j]+1 | j右端<=i左端 }

邊界條件 F[0]=0

目標結果

F[N+1]-1

==1119==

這道題有明顯的動態規劃策略。首先不要按照方格來考慮，考慮頂點，這樣目標點就是(N+1,M+1)。

———算法1———– 最直觀的想法是按照矩陣動態規劃。

設狀態F[i,j]爲走到點(i,j)時的最短路徑

狀態轉移方程 F[i,j]=Min { F[i-1,j]+100 F[i,j-1]+100 F[i-1,j-1]+141.4213562373 }

邊界條件 F[0,0]=0

F[N+1,M+1]就是結果。

但是對於8M的內存限制，要使用滾動數組。

時間複雜度爲O(N*M)

———算法2———– 可以發現，如果我們只走直邊的話，要走(N+M)100長度。如果走C條斜邊，那麼要走(C141.4213562373)+(N+M-C*2)*100 的長度。那麼顯然我們要儘可能使C更大，即多走斜邊。

這樣可以轉化爲經典的LIS模型。即把所有的斜邊按照座標排序，然後求最長的上升序列(x，y都要嚴格遞增)，走這樣的斜邊一定是最優的策略。於是我們可以求出C。

結果就是(C141.4213562373)+(N+M-C2)*100。

Vijos 1336其實就是這道題的數據加大版。對於較小的K和很大的N,M，只能用算法2解決。

==1138==

看似簡單，很容易出錯的動態規劃。我用了正向遞推的方法。注意每次最大增量爲100%，最後的結果不是到n的最大次數，而是小於等於n的最大次數。

設狀態 F[i] 爲薪水達i時，從最初的薪水到i時最大數目。F[i]爲0時代表無法到達。

狀態轉移方程 F[j]=Max{ F[j],F[i]+1 } i=s..n-1 且F[i]不爲0 k=1..100 表示增量如果ik整除100，則j=i+ik/100。

邊界條件 F[s]=1

目標結果 Max{ F[i] | i=s..n }

==1146==

最大子矩陣問題。對於這個問題，首先要把它轉化成最大連續序列和問題然後再進行動態規劃。思路爲把矩陣“壓縮”成一個序列。

對於矩陣，首先對每一行掃描，求出每行上任意一段序列和，時間複雜度爲O(N^2)然後枚舉每個段，對每行的這個段進行動態規劃。

例如下列矩陣 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 當我們枚舉到每行[1,2]，可以“壓縮”爲 -2 11 -3 7 對這個序列求最大連續序列和，即可求出當前位置邊長的最大子矩陣。時間複雜度爲O(N)，分別枚舉每個段，時間複雜度爲O(N^2)，總時間複雜度爲O(N^3)。

動態規劃狀態設定 F[i,j]爲矩陣第i行，前j項和。則可知第k行從i到j項和可表示爲F[k,j]-F[j,i-1]。 G[i,j,k]爲對於從i到j項的一段，以第k行爲尾的前k行的每行項的最大和。

狀態轉移方程 F[i,j]=F[i,j-1] + Number[i,j] G[i,j,k]=Max{ G[i,j,k-1] + F[k,j]-F[j,i-1] , F[k,j]-F[j,i-1] }

目標解爲 Max { G[i,j,k] }

以下是代碼 ==1102==

#include <iostream>
#define MAX 4000001
using namespace std;

int N,L;
char S[MAX];
bool F[MAX];
char W[6][10]={"one","puton","out","in","input","output"};
int Len[6];

void init()
{
	int i;
	freopen("1102.in","r",stdin);
	freopen("1102.out","w",stdout);
	scanf("%d\n",&N);
	for (i=0;i<6;i++)
		Len[i]=strlen(W[i]);
}

bool match(char *S,char *k)
{
	for (;*k;k++,S++)
		if (*k!=*S)
			return false;
	return true;
}

bool dynamic()
{
	int i,j;
	F[0]=true;
	for (i=1;i<=L;i++)
	{
		F[i]=false;
		for (j=0;j<6;j++)
		{
			if (i-Len[j]>=0 && match(&S[i-Len[j]+1],W[j]))
			{
				if (F[i-Len[j]])
				{
					F[i]=true;
					break;
				}
			}
		}
	}
	return F[L];
}

int main()
{
	init();
	for (int i=1;i<=N;i++)
	{
		scanf("%s",S+1);
		L=strlen(S+1);
		memset(F,0,sizeof(F));
		bool yes=dynamic();
		if (yes)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

==1112== ```cpp #include #define MAX 100 using namespace std;

struct interval { int left,right; };

int N,Ans; interval S[MAX]; int F[MAX],G[MAX],A[MAX];

template void SWAP(T &a,T &b) { T c=a;a=b;b=c; }

int cmp(const void *a,const void *b) { if (((interval *)a)->left< ((interval *)b)->left) return -1; if (((interval *)a)->right< ((interval *)b)->right) return -1; return 1; }

void init() { int i; freopen(“1112.in”,“r”,stdin); freopen(“1112.out”,“w”,stdout); cin » N; for (i=1;i<=N;i++) { cin » S[i].left » S[i].right; if (S[i].left > S[i].right) SWAP(S[i].left,S[i].right); } qsort(S+1,N,sizeof(S[0]),cmp); }

void dynamic() { int i,j; S[0].left=S[0].right=-1000; S[N+1].left=S[N+1].right=1000; for (i=1;i<=N+1;i++) { for (j=0;j<i;j++) { if (S[i].left>=S[j].right && F[j]+1>F[i]) { F[i]=F[j]+1; G[i]=j; } } } Ans=F[N+1]-1; cout « Ans « endl; for (i=G[N+1];i;i=G[i],Ans–) A[Ans]=i; for (i=1;i<=F[N+1]-1;i++) cout « S[A[i]].left « ’ ’ « S[A[i]].right « endl; }

int main() { init(); dynamic(); return 0; }

<hr />
==1119==

===算法一===
```cpp
#include <iostream>

using namespace std;

const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;

int M,N,P;
bool cross[MAX][MAX];
double F[2][MAX];

void init()
{
	int i,a,b;
	freopen("1119.in","r",stdin);
	freopen("1119.out","w",stdout);
	cin >> M >> N >> P;
	N++;M++;
	for (i=1;i<=P;i++)
	{
		cin >> b >> a;
		a++;b++;
		cross[a][b]=true;
	}
	cross[1][1]=true;
	F[0][0]=-Dc;
}

void dynamic()
{
	int i,j,p;
	double min;
	for (i=p=1;i<=N;i++,p=!p)
	{
		for (j=1;j<=M;j++)
		{
			min=INF;
			if (i>1 && F[!p][j] + Dl <min)
			{
				min=F[!p][j] + Dl;
			}
			if (j>1 && F[p][j-1] + Dl <min)
			{
				min=F[p][j-1] + Dl;
			}
			if (cross[i][j] && F[!p][j-1] + Dc < min)
			{
				min=F[!p][j-1] + Dc;
			}
			F[p][j]=min;
		}
	}
	printf("%.0lf",F[!p][M]);
}

int main()
{
	init();
	dynamic();
	return 0;
}

===算法二===

#include <iostream>

using namespace std;

const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;

struct Point
{
	int x,y;
};

int M,N,P;
Point T[MAX];
int F[MAX];
double Ans;

inline int cmp(const void *a,const void *b)
{
	if (((Point *)a)->x==((Point *)b)->x && ((Point *)a)->y<((Point *)b)->y)
		return -1;
	return ((Point *)a)->x < ((Point *)b)->x ?-1 :1;
}

void init()
{
	int i,a,b;
	freopen("1119.in","r",stdin);
	freopen("1119.out","w",stdout);
	cin >> M >> N >> P;
	N++;M++;
	for (i=1;i<=P;i++)
	{
		cin >> b >> a;
		a++;b++;
		T[i].x=a;
		T[i].y=b;
	}
	qsort(T+1,P,sizeof(T[0]),cmp);
}

void dynamic()
{
	int i,j,max,cnt=0,d;
	for (i=1;i<=P;i++)
	{
		max=0;
		for (j=0;j<=i-1;j++)
		{
			if (T[j].x<T[i].x && T[j].y<T[i].y &&  F[j] + 1 > max)
				max=F[j]+1;
		}
		F[i]=max;
		if (F[i]>cnt)
			cnt=F[i];
	}
	d=N+M-cnt*2-2;
	Ans=d*Dl + cnt*Dc;
	printf("%.0lf",Ans);
}

int main()
{
	init();
	dynamic();
	return 0;
}

==1138== ```cpp #include

using namespace std;

const int MAX=10001;

int A,B,Ans; int F[MAX];

void init() { freopen(“1138.in”,“r”,stdin); freopen(“1138.out”,“w”,stdout); cin » B » A; }

void dynamic() { int i,j,k; Ans=F[A]=1; for (i=A;i<=B-1;i++) { if (!F[i]) continue; for (k=1;k<=100;k++) if (ik%100==0) { j=i+ik/100; if (j>B) continue; if (F[i]+1>F[j]) F[j]=F[i]+1; if (F[j]>Ans) Ans=F[j]; } } }

int main() { init(); dynamic(); cout « Ans; return 0; }

<hr />
==1146==
```cpp
#include <iostream>

using namespace std;

const int MAX=101;
const int INF=0x7FFFFFFF;

int Num[MAX][MAX],F[MAX][MAX];
int G[MAX];
int N,Ans=-INF;

void init()
{
	int i,j;
	freopen("1146.in","r",stdin);
	freopen("1146.out","w",stdout);
	cin >> N;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			scanf("%d",&Num[i][j]);
		}
	}
}

void dynamic()
{
	int i,j,k,Item;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			F[i][j]=F[i][j-1]+Num[i][j];
		}
	}

	for (i=1;i<=N;i++)
	{
		for (j=i;j<=N;j++)
		{
			for (k=1;k<=N;k++)
			{
				Item=F[k][j]-F[k][i-1];
				if (G[k-1] + Item > Item)
					G[k]=G[k-1] + Item ;
				else
					G[k]=Item;
				if (G[k]>Ans)
					Ans=G[k];
			}
		}
	}
}

int main()
{
	init();
	dynamic();
	cout << Ans ;
	return 0;
}

上次修改時間 2017-02-03

相關日誌