NOI 2009 詩人小G

本文正體字版由OpenCC轉換

問題簡述

有N個詩句需要被排版爲若干行，順序不能改變。一行內可以有若干個詩句，相鄰詩句之間有一個空格。定義行標準長度L，每行的不協調度爲|實際長度-L|^P，整首詩的不協調度就是每行不協調度之和。任務是安排一種排版方案，使得整首詩的不協調度最小。

問題建模

這是一個最優化問題，抽象成動態規劃模型。設第i個詩句的長度爲Len[i]，前i個詩句的總長度爲SumL[i]，。F[i]爲對前i個詩句排版的最小不協調度。

解法1 樸素的動態規劃

算法描述

顯然每個F[i]可以被分解爲F[j]和第j+1…i個句子組成一行的狀態，所以狀態轉移方程爲

簡化後，可以書寫成

在具體實現時，應記錄每個狀態的決策，以便於輸出合法方案。考慮到“最小的不協調度超過10¹⁸輸出"Too hard to arrange"”，爲防止64位整型運算溢出，可以先用浮點數類型計算，然後再用整型算出具體值。

複雜度分析

狀態數爲O(N)，每次轉移需要以O(N)的時間枚舉j，所以時間複雜度爲O(N²)。在實際測試中通過了測試點1，2，3，得到30分。

參考程序

```cpp /* * Problem: NOI2009 poet * Author: Guo Jiabao * Time: 2009.9.22 13:30 * State: Solved * Memo: 樸素動態規劃 */ #include #include #include #include #include using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32; const big INF=~0ULL»1,LIMIT=1000000000000000000LL;

big F[MAXN],sumL[MAXN]; int N,L,P; int Len[MAXN],deci[MAXN],sel[MAXN]; char sent[MAXN][SMAXL];

void init() { scanf("%d%d%d\n",&N,&L,&P); for (int i=1;i<=N;++i) { gets(sent[i]); Len[i] = strlen(sent[i]); sumL[i] = sumL[i-1] + Len[i]; } }

big power(big a) { big t=1; double dt=1; if (a < 0) a = -a; for (int i=1;i<=P;i++) { dt *= a; if (dt > LIMIT) return INF; t *= a; } return t; }

void solve() { int i,j,k; big minv,t; for (i=1;i<=N;++i) { minv = INF; for (j=0;j<=i-1;++j) { t = power(sumL[i] - sumL[j] + i-j-1 - L); if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv) { minv = t + F[j]; k = j; } } F[i] = minv; deci[i] = k; } }

void print() { if (F[N] <= LIMIT) { cout « F[N] « endl; int i,j; for (i=N,j=0;i;i=deci[i]) sel[++j] = i; for (i=0;j;j–) { for (++i;i < sel[j];++i) printf("%s “,sent[i]); printf("%s\n”,sent[i]); } } else printf(“Too hard to arrange\n”); printf("——————–\n"); }

int main() { int i,T; freopen(“poet.in”,“r”,stdin); freopen(“poet.out”,“w”,stdout); scanf("%d",&T); for (i=1;i<=T;i++) { init(); solve(); print(); } return 0; }


<h4>解法2 貪心的動態規劃</h4>

<h5>算法描述</h5>
觀察測試點4，5的N值較大，而L值較小，因此可以限制每行長度，以優化狀態轉移。

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image008_thumb.gif"><img title="clip_image008" src="https://byvoid.com/attachments/wp/2010/01/clip_image008_thumb.gif" alt="clip_image008" width="455" height="55" /></a>

實現時應讓j從i-1到0枚舉，當j&lt;i-1時一旦發現行長度超過2L，即停止枚舉j，因爲j繼續減少會讓行長度繼續增加。
<h5>算法證明</h5>
一個空行的不協調度爲L<sup>P</sup>，若一行內包含多餘一個句子，且行長度L’&gt;2L，則行不協調度(L’-L)<sup>P</sup>&gt;L<sup>P</sup>。把該行拆分爲兩行後，設長度分別爲L1和L2，L1+L2=L’-1，拆分後的兩行不協調度之和爲(L1-L)P+(L2-L)P&lt;(L’-L)<sup>P</sup>，所以拆分爲兩行後比合在一行好。因此應保證當一行包含多於一個句子時，行長度&lt;=2L。
<h5>複雜度分析</h5>
狀態數爲O(N)，每次轉移需要O(Min{N,L})的時間，所以時間複雜度爲O(Min{N<sup>2</sup>,NL})。在實際測試中通過了前5個測試點，得到50分。
<h5>參考程序</h5>
```cpp
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 13:51
 * State: Solved
 * Memo: 樸素動態規劃 剪枝
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big INF=~0ULL>>1,LIMIT=1000000000000000000LL;

big F[MAXN],sumL[MAXN];
int N,L,P;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];

void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}

big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return INF;
		t *= a;
	}
	return t;
}

void solve()
{
	int i,j,k;
	big minv,t;
	for (i=1;i<=N;++i)
	{
		minv = INF;
		for (j=i-1;j>=0;--j)
		{
			t = sumL[i] - sumL[j] + i-j-1 - L;
			if (j < i-1 && t > L + L)
				break;
			t = power(t);
			if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv)
			{
				minv = t + F[j];
				k = j;
			}
		}
		F[i] = minv;
		deci[i] = k;
	}
}

void print()
{
	if (F[N] <= LIMIT)
	{
		cout << F[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}

int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

解法3 凸殼優化動態規劃

算法描述

觀察發現測試點6，7的N和L都很大，而P值爲2。經分析發現可以使用單調隊列維護凸殼。

算法分析與證明

當P=2時，觀察狀態轉移方程

設對於F[i]的最優決策爲k，那麼對於所有的j≠k，均滿足

設，，則有

因爲SumL爲單調增函數，所以A，B均爲增函數。當B[j]>B[k] ⇒j>k，有

相對的，當j<k時有

如果把(B[i],F[i]+B[i]²)看作是二維平面上的一個點，那麼恰爲斜率公式。因此對於最優決策k，應保證在對應點右邊任意一個決策j的對應點，滿足直線kj斜率大於2A[i]；在對應點左邊任意一個決策j的對應點，滿足直線kj斜率小於2A[i]。

因此所有最優決策在平面上的對應點連線就是一個斜率遞增的凸殼。

具體實現時，用單調隊列維護每個點(B[i],F[i]+B[i]²)，每在隊尾加入一個新的點，判斷斜率是否遞增，如果不是則不斷刪除隊尾元素。求F[i]的最優決策只需不斷在隊首刪除點，直到隊首兩點組成的直線斜率剛好大於2A[i]，最優決策就是左端點的對應決策。

複雜度分析

用單調隊列每次維護凸殼的時間複雜度爲均攤O(1)，所以時間複雜度爲O(N)。經測試可以通過測試點6，7，配合解法2，一共可以得到70分。

參考程序

```cpp /* * Problem: NOI2009 poet * Author: Guo Jiabao * Time: 2009.9.22 14:30 * State: Solved * Memo: 樸素動態規劃剪枝凸殼優化 */ #include #include #include #include #include using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32; const big INF=~0ULL»1,LIMIT=1000000000000000000LL;

struct MonoQueue { struct point { big x,y; int id; }P[MAXN];

int head,tail;

void initialize()
{
	head = 0;
	tail = -1;
}

void insert(big x,big y,int id)
{
	point p={x,y,id};
	for (;head + 1 <= tail;--tail)
	{
		double k1,k2;
		k1 = (p.y - P[tail].y) / double(p.x - P[tail].x);
		k2 = (P[tail].y - P[tail-1].y) / double(P[tail].x - P[tail-1].x);
		if (k1 > k2)
			break;
	}
	P[++tail] = p;
}

int getmin(big v)
{
	for (;head + 1 <= tail;++head)
	{
		double k = (P[head+1].y - P[head].y) / double(P[head+1].x - P[head].x);
		if (k > v)
			break;
	}
	return P[head].id;
}

}MQ;

big F[MAXN],sumL[MAXN],A[MAXN],B[MAXN]; int N,L,P; int Len[MAXN],deci[MAXN],sel[MAXN]; char sent[MAXN][SMAXL];

void init() { scanf("%d%d%d\n",&N,&L,&P); for (int i=1;i<=N;++i) { gets(sent[i]); Len[i] = strlen(sent[i]); sumL[i] = sumL[i-1] + Len[i]; } }

big power(big a) { big t=1; double dt=1; if (a < 0) a = -a; for (int i=1;i<=P;i++) { dt *= a; if (dt > LIMIT) return INF; t *= a; } return t; }

void tq() { int i,j; big t; MQ.initialize(); MQ.insert(0,0,0); for (i=1;i<=N;i++) { B[i] = sumL[i] + i; A[i] = B[i] - 1 - L; } for (i=1;i<=N;i++) { j = MQ.getmin(A[i] + A[i]); t = power(sumL[i] - sumL[j] + i-j-1 - L); if ( double(t) + double(F[j]) <= LIMIT ) F[i] = F[j] + t; else F[i] = INF; if ( double(B[i]) * double(B[i]) + F[i] <= LIMIT) t = F[i] + B[i] * B[i]; else t = INF; MQ.insert(B[i],t,i); deci[i] = j; } }

void simple() { int i,j,k; big minv,t; k = -1; for (i=1;i<=N;++i) { minv = INF; for (j=i-1;j>=0;–j) { t = sumL[i] - sumL[j] + i-j-1 - L; if (t > L + L) break; t = power(t); if ( double(t) + double(F[j]) <= LIMIT && t + F[j] < minv) { minv = F[j] + t; k = j; } } F[i] = minv; deci[i] = k; } }

void solve() { if (P == 2) tq(); else simple(); }

int main() { int i,T; freopen(“poet.in”,“r”,stdin); freopen(“poet.out”,“w”,stdout); scanf("%d",&T); for (i=1;i<=T;i++) { init(); solve(); print(); } return 0; }


<h4>解法4 決策單調性優化動態規劃</h4>

<h5>算法描述</h5>
可以觀察到或證明出，該狀態轉移方程滿足決策單調性。因此我們可以使用雙端隊列維護每個決策區間，對於每個新決策使用二分查找確定位置並更新決策隊列。
<h5>算法證明</h5>
再次觀察狀態轉移方程

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image034_thumb.gif"><img title="clip_image034" src="https://byvoid.com/attachments/wp/2010/01/clip_image034_thumb.gif" alt="clip_image034" width="371" height="37" /></a><strong> </strong>

設<a href="https://byvoid.com/attachments/wp/2010/01/clip_image036_thumb.gif"><img title="clip_image036" src="https://byvoid.com/attachments/wp/2010/01/clip_image036_thumb.gif" alt="clip_image036" width="282" height="37" /></a>，狀態轉移方程可以化爲1D/1D標準形式

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image038_thumb.gif"><img title="clip_image038" src="https://byvoid.com/attachments/wp/2010/01/clip_image038_thumb.gif" alt="clip_image038" width="164" height="37" /></a>

要證明上述狀態轉移方程具有決策單調性，k(i)表示F[i]的最優決策，即

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image040_thumb.gif"><img title="clip_image040" src="https://byvoid.com/attachments/wp/2010/01/clip_image040_thumb.gif" alt="clip_image040" width="104" height="37" /></a>

當且僅當滿足四邊形不等式

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image042_thumb.gif"><img title="clip_image042" src="https://byvoid.com/attachments/wp/2010/01/clip_image042_thumb.gif" alt="clip_image042" width="359" height="37" /></a>

設<a href="https://byvoid.com/attachments/wp/2010/01/clip_image044_thumb.gif"><img title="clip_image044" src="https://byvoid.com/attachments/wp/2010/01/clip_image044_thumb.gif" alt="clip_image044" width="107" height="37" /></a>，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image046_thumb.gif"><img title="clip_image046" src="https://byvoid.com/attachments/wp/2010/01/clip_image046_thumb.gif" alt="clip_image046" width="101" height="37" /></a>，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image048_thumb.gif"><img title="clip_image048" src="https://byvoid.com/attachments/wp/2010/01/clip_image048_thumb.gif" alt="clip_image048" width="58" height="37" /></a>。其中<a href="https://byvoid.com/attachments/wp/2010/01/clip_image050_thumb.gif"><img title="clip_image050" src="https://byvoid.com/attachments/wp/2010/01/clip_image050_thumb.gif" alt="clip_image050" width="148" height="37" /></a>。

於是<a href="https://byvoid.com/attachments/wp/2010/01/clip_image052_thumb.gif"><img title="clip_image052" src="https://byvoid.com/attachments/wp/2010/01/clip_image052_thumb.gif" alt="clip_image052" width="152" height="37" /></a>。要證明①，只需證明

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image054_thumb.gif"><img title="clip_image054" src="https://byvoid.com/attachments/wp/2010/01/clip_image054_thumb.gif" alt="clip_image054" width="570" height="37" /></a>

設<a href="https://byvoid.com/attachments/wp/2010/01/clip_image056_thumb.gif"><img title="clip_image056" src="https://byvoid.com/attachments/wp/2010/01/clip_image056_thumb.gif" alt="clip_image056" width="107" height="37" /></a>，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image058_thumb.gif"><img title="clip_image058" src="https://byvoid.com/attachments/wp/2010/01/clip_image058_thumb.gif" alt="clip_image058" width="133" height="37" /></a>，則②等價於

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image060_thumb.gif"><img title="clip_image060" src="https://byvoid.com/attachments/wp/2010/01/clip_image060_thumb.gif" alt="clip_image060" width="273" height="37" /></a>

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image062_thumb.gif"><img title="clip_image062" src="https://byvoid.com/attachments/wp/2010/01/clip_image062_thumb.gif" alt="clip_image062" width="301" height="37" /></a>

因爲<a href="https://byvoid.com/attachments/wp/2010/01/clip_image064_thumb.gif"><img title="clip_image064" src="https://byvoid.com/attachments/wp/2010/01/clip_image064_thumb.gif" alt="clip_image064" width="98" height="37" /></a>，且D[i+1]恆爲正數，所以S&lt;T。於是要證明③，只需證明下列函數在整數域內(非嚴格)單調遞增

<a href="https://byvoid.com/attachments/wp/2010/01/clip_image066_thumb.gif"><img title="clip_image066" src="https://byvoid.com/attachments/wp/2010/01/clip_image066_thumb.gif" alt="clip_image066" width="249" height="37" /></a><strong></strong>
<h6>(1)若P爲偶數</h6>
<a href="https://byvoid.com/attachments/wp/2010/01/clip_image068_thumb.gif"><img title="clip_image068" src="https://byvoid.com/attachments/wp/2010/01/clip_image068_thumb.gif" alt="clip_image068" width="120" height="37" /></a>，求導得<a href="https://byvoid.com/attachments/wp/2010/01/clip_image070_thumb.gif"><img title="clip_image070" src="https://byvoid.com/attachments/wp/2010/01/clip_image070_thumb.gif" alt="clip_image070" width="169" height="37" /></a>。

因爲<a href="https://byvoid.com/attachments/wp/2010/01/clip_image072_thumb.gif"><img title="clip_image072" src="https://byvoid.com/attachments/wp/2010/01/clip_image072_thumb.gif" alt="clip_image072" width="56" height="37" /></a>，P-1爲奇數，所以<a href="https://byvoid.com/attachments/wp/2010/01/clip_image074_thumb.gif"><img title="clip_image074" src="https://byvoid.com/attachments/wp/2010/01/clip_image074_thumb.gif" alt="clip_image074" width="131" height="37" /></a>，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image076_thumb.gif"><img title="clip_image076" src="https://byvoid.com/attachments/wp/2010/01/clip_image076_thumb.gif" alt="clip_image076" width="54" height="37" /></a>恆成立，f(x)在實數域內單調遞增。
<h6>(2)若P爲奇數</h6>
<h6>(a)當X-C&gt;=0</h6>
<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0681_thumb.gif"><img title="clip_image068[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0681_thumb.gif" alt="clip_image068[1]" width="120" height="37" /></a>，求導得<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0701_thumb.gif"><img title="clip_image070[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0701_thumb.gif" alt="clip_image070[1]" width="169" height="37" /></a>。

因爲<a href="https://byvoid.com/attachments/wp/2010/01/clip_image080_thumb.gif"><img title="clip_image080" src="https://byvoid.com/attachments/wp/2010/01/clip_image080_thumb.gif" alt="clip_image080" width="82" height="37" /></a>，P-1爲偶數，所以<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0741_thumb.gif"><img title="clip_image074[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0741_thumb.gif" alt="clip_image074[1]" width="131" height="37" /></a>，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0761_thumb.gif"><img title="clip_image076[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0761_thumb.gif" alt="clip_image076[1]" width="54" height="37" /></a>恆成立，f(x)在實數域內單調遞增。
<h6>(b)當X&lt;=0</h6>
<a href="https://byvoid.com/attachments/wp/2010/01/clip_image084_thumb.gif"><img title="clip_image084" src="https://byvoid.com/attachments/wp/2010/01/clip_image084_thumb.gif" alt="clip_image084" width="142" height="37" /></a>，求導得<a href="https://byvoid.com/attachments/wp/2010/01/clip_image086_thumb.gif"><img title="clip_image086" src="https://byvoid.com/attachments/wp/2010/01/clip_image086_thumb.gif" alt="clip_image086" width="172" height="37" /></a>。因爲P-1爲偶數，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0762_thumb.gif"><img title="clip_image076[2]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0762_thumb.gif" alt="clip_image076[2]" width="54" height="37" /></a>恆成立，f(x)在實數域內單調遞增。
<h6>(c)當0&lt;X&lt;C</h6>
<a href="https://byvoid.com/attachments/wp/2010/01/clip_image090_thumb.gif"><img title="clip_image090" src="https://byvoid.com/attachments/wp/2010/01/clip_image090_thumb.gif" alt="clip_image090" width="120" height="37" /></a>，求導得<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0861_thumb.gif"><img title="clip_image086[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0861_thumb.gif" alt="clip_image086[1]" width="172" height="37" /></a>。因爲P-1爲偶數，<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0763_thumb.gif"><img title="clip_image076[3]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0763_thumb.gif" alt="clip_image076[3]" width="54" height="37" /></a>恆成立，f(x)在實數域內單調遞增。

綜上所述，f(x)在實數域內單調遞增，即在正數域內單調遞增，因而③②①依次得證。

因此狀態轉移方程<a href="https://byvoid.com/attachments/wp/2010/01/clip_image0061_thumb.gif"><img title="clip_image006[1]" src="https://byvoid.com/attachments/wp/2010/01/clip_image0061_thumb.gif" alt="clip_image006[1]" width="357" height="37" /></a>具有決策單調性。
<h5>複雜度分析</h5>
狀態數爲O(N)，每次維護決策隊列的時間爲O(logN)，所以時間複雜度爲O(NlogN)。在測試中通過了全部測試點，拿到了100分。
<h5>參考程序</h5>
```cpp
/* 
 * Problem: NOI2009 poet
 * Author: Guo Jiabao
 * Time: 2009.9.22 16:30
 * State: Solved
 * Memo: 動態規劃 決策單調性
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN=100001,SMAXL=32;
const big LIMIT=1000000000000000000LL;

struct interval
{
	int s,t,deci;
}di[MAXN];

double F[MAXN];
int N,L,P,Stop;
int Len[MAXN],deci[MAXN],sel[MAXN];
char sent[MAXN][SMAXL];
big G[MAXN],sumL[MAXN];

void init()
{
	scanf("%d%d%d\n",&N,&L,&P);
	for (int i=1;i<=N;++i)
	{
		gets(sent[i]);
		Len[i] = strlen(sent[i]);
		sumL[i] = sumL[i-1] + Len[i];
	}
}

double dpower(double a)
{
	double t=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
		t *= a;
	return t;
}

double getF(int i,int j)
{
	double t = dpower(sumL[i] - sumL[j] + i-j-1 - L);
	return F[j] + t;
}

big power(big a)
{
	big t=1;
	double dt=1;
	if (a < 0)
		a = -a;
	for (int i=1;i<=P;i++)
	{
		dt *= a;
		if (dt > LIMIT)
			return LIMIT+1;
		t *= a;
	}
	return t;
}

big getG(int i,int j)
{
	big t = power(sumL[i] - sumL[j] + i-j-1 - L);
	if (F[j] + t <= LIMIT)
		return G[j] + t;
	else
		return LIMIT + 1;
}

void update(int i)
{
	while (di[Stop].s > i && getF(di[Stop].s,i) < getF(di[Stop].s,di[Stop].deci) )
	{
		di[Stop-1].t = di[Stop].t;
		Stop --;
	}
	int a=di[Stop].s,b=di[Stop].t,m;
	if (a < i+1)
		a = i+1;
	while (a+1<b)
	{
		m = (a + b) >> 1;
		if ( getF(m,di[Stop].deci) < getF(m,i) )
			a = m;
		else
			b = m-1;
	}
	if ( a < b && getF(b,di[Stop].deci) < getF(b,i) )
		a = b;
	if (a+1 <= di[Stop].t)
	{
		di[Stop + 1].s = a+1;
		di[Stop + 1].t = di[Stop].t;
		di[Stop + 1].deci = i;
		di[Stop].t = a;
		++Stop;
	}
}

void solve()
{
	int i,j;
	di[Stop=1].s = 1;
	di[Stop].t = N;
	for (i=j=1;i<=N;i++)
	{
		if (i > di[j].t)
			++j;
		deci[i] = di[j].deci;
		F[i] = getF(i,deci[i]);
		update(i);
	}
	for (i=1;i<=N;i++)
		G[i] = getG(i,deci[i]);
}

void print()
{
	if (G[N] <= LIMIT)
	{
		cout << G[N] << endl;
		int i,j;
		for (i=N,j=0;i;i=deci[i])
			sel[++j] = i;
		for (i=0;j;j--)
		{
			for (++i;i < sel[j];++i)
				printf("%s ",sent[i]);
			printf("%s\n",sent[i]);
		}
	}
	else
		printf("Too hard to arrange\n");
	printf("--------------------\n");
}

int main()
{
	int i,T;
	freopen("poet.in","r",stdin);
	freopen("poet.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		solve();
		print();
	}
	return 0;
}

上次修改時間 2017-05-26

問題簡述

問題建模

解法1 樸素的動態規劃

算法描述

複雜度分析

參考程序

解法3 凸殼優化動態規劃

算法描述

算法分析與證明

複雜度分析

參考程序

相關日誌