1.洛谷 P4342 IOI1998 Polygon

我的博客

2.洛谷 P4290 HAOI2008 玩具取名

題意

某人有一套玩具，并想法給玩具命名。首先他選擇 W, I, N, G 四個字母中的任意一個字母作為玩具的基本名字。然后他會根據自己的喜好，將名字中任意一個字母用 W, I, N, G 中任意兩個字母代替，使得自己的名字能夠擴充得很長。

現在，他想請你猜猜某一個很長的名字，最初可能是由哪幾個字母變形過來的。

四個整數 $W,I,N,G$，表示每一個字母能由幾種兩個字母所替代：

• 接下來 $W$ 行，每行兩個字母,表示 W 可以用這兩個字母替代。

• 接下來 $I$ 行，每行兩個字母，表示 I 可以用這兩個字母替代。

• 接下來 $N$ 行，每行兩個字母，表示 N 可以用這兩個字母替代。

• 接下來 $G$ 行，每行兩個字母，表示 G 可以用這兩個字母替代。

• 最后一行一個長度不超過 $L$ 的字符串。表示這個玩具的名字。

一行字符串，輸出該名字可能由哪一個字母變形而得到。（按照 W, I, N, G 的順序輸出）

如果給的名字不能由任何一個字母變形而得到則輸出 The name is wrong!。

$L\le 200$，$W,I,N,G\le 16$。

思路

其實就是原字符串中，找其中兩個合并成特定的一個字母，問最后能否變成只有一個字母。合并問題，想到用區間 dp。

不妨給 $4$ 個字母編號：$\mathrm{W},\mathrm{I},\mathrm{N},\mathrm{G}$ 分別對應 $1,2,3,4$。設 $f_{i,j,x}$ 表示區間 $[i,j]$ 的字符，是否可以合并成編號為 $x$ 的字符。

考慮轉化為子問題：將區間 $[i,j]$ 拆分成 $[i,k]$ 和 $[k+1,j]$，并且分別期望用編號為 $pq,p,q$ 的字母來覆蓋（這變量夠直觀吧）。

如果左右區間都可以被完全替換為期望字符，并且編號為 $pq$ 的字母可以被兩個編號分別為 $p,q$ 的字母并起來替代，那么 $f_{i,j,x}=1$。

至于關系就很好處理了。我的代碼是懶人寫法：

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=203;
ll m[5];
string s;
bool vis[5][5][5],f[N][N][5];//f(i,j,x):區間[i,j]能否替換成字母編號x 
ll chg(char c)
{if(c=='W')return 1;if(c=='I')return 2;if(c=='N')return 3;return 4;
}
char print(ll i)
{if(i==1)return 'W';if(i==2)return 'I';if(i==3)return 'N';return 'G';
}
int main()
{ios::sync_with_stdio(0);for(int i=1;i<=4;i++)cin>>m[i];for(int i=1;i<=4;i++){for(int j=1;j<=m[i];j++){string t;cin>>t;vis[i][chg(t[0])][chg(t[1])]=1;}}cin>>s;ll n=s.size();s='*'+s;for(int i=1;i<=n;i++)f[i][i][chg(s[i])]=1;for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){ll j=i+len-1;for(int k=i;k<j;k++)for(int pq=1;pq<=4;pq++)for(int p=1;p<=4;p++)for(int q=1;q<=4;q++)if(vis[pq][p][q]&&f[i][k][p]&&f[k+1][j][q])f[i][j][pq]=1;}}bool flag=0;for(int pq=1;pq<=4;pq++){if(f[1][n][pq])cout<<print(pq);flag|=f[1][n][pq];}if(!flag)puts("The name is wrong!");return 0;
}

3.CF607B Zuma

題意

$\text{Genos}$ 最近在他的手機上下載了祖瑪游戲。在祖瑪游戲里，存在 $n$ 個一行的寶石，第 $i$ 個寶石的顏色是 $a_i$。這個游戲的目標是盡快的消滅一行中所有的寶石。

在一秒鐘，$\text{Genos}$ 能很快的挑選出這些有顏色的寶石中的一個回文的、連續的子串，并將這個子串移除。每當一個子串被刪除后，剩余的寶石將連接在一起，形成一個新的行列。

求把整個寶石串都移除的最短時間。

$1\le n\le 500$。

思路

合并就考慮區間 dp，設 $f_{i,j}$ 表示區間 $[i,j]$ 能否被完全消除，那么有幾個明顯的結論：

• $f_{i,i}=1$
• $f_{i,i+1}=\{\begin{array}{c}1,a_i=a_{i+1}\\ 2,a_i\ne a_{i+1}\end{array}$
• $f_{i,j}=f_{i+1,j?1},a_i=a_j$

前兩點用于初始化。第三點作為特殊情況；對于樸素情況，枚舉斷點 $k\in [i,j)$ 就好：
f i , j = min ? { f i , k + f k + 1 , j } f_{i,j}=\min\{f_{i,k}+f_{k+1,j}\} fi,j?=min{fi,k?+fk+1,j?}

只需討論區間長度為 $3$ 的就好了。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=502,inf=0x3f3f3f3f;
ll n,a[N];
ll f[N][N];//f(i,j):區間[i,j]全部消除的最短時間 
bool palin(ll l,ll r)
{for(int i=l,j=r;i<=j;i++,j--)if(a[i]!=a[j])return 0;return 1;
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){f[i][i]=1;if(a[i]==a[i+1])f[i][i+1]=1;else f[i][i+1]=2;for(int j=i+2;j<=n;j++)f[i][j]=inf;}for(int len=3;len<=n;len++){for(int i=1;i+len-1<=n;i++){ll j=i+len-1;if(a[i]==a[j])f[i][j]=f[i+1][j-1];for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);}}printf("%lld",f[1][n]);return 0;
}