動态規劃之區間DP專題

什麼是區間DP

所謂區間dp,就是在一個區間上進行的dp， 一般通過将大區間分割成小區間進行dp。

區間型動态規劃，又稱為合并類動态規劃，是線性動态規劃的擴充，它在分階段地劃分問題時，與階段中元素出現的順序和由前一階段的區間中哪些元素合并而來有很大的關系。

區間動歸狀态轉移方程及一般動規過程：

for k:= to n- do    //區間長度
  for i:= to n-k do     //區間起點
    for j:=i to i+k- do     //區間中任意點
      dp[i,i+k]:=max{dp[i,j] + dp[j+,i+k] + a[i,j] + a[j+,i+k]};
           

1. 狀态轉移方程字面意義：尋找區間dp[i,i+k]的一種合并方式dp[i,j] + dp[j+1,i+k]，使得其值最大或最小。
2. 區間長度k必須要放到第一層循環，來保證方程中狀态dp[i,j]、dp[j+1,i+k]值在dp[i,i+k]之前就已計算出來。
3. 其中a[i,j]+a[j+1,i+k]可以不要，也可以靈活多變，指的是合并區間時産生的附加值。
           

【NOI1995】石子合并

【線上測試送出傳送門】

【問題描述】

在一個圓形操場的四周擺放N堆石子,現要将石子有次序地合并成一堆。規定每次隻能選相鄰的2堆合并成新的一堆，并将新的一堆的石子數，記為該次合并的得分。
  設計出1個算法,計算出将N堆石子合并成1堆的最小得分和最大得分。
      

【輸入格式】

資料的第1行試正整數N,1≤N≤100,表示有N堆石子.第2行有N個數,分别表示每堆石子的個數。
      

【輸出格式】

輸出共2行,第1行為最小得分,第2行為最大得分。
      

【輸入樣例1】

4
4 5 9 4
      

【輸出樣例1】

43
54
      

【解題思路】

看到題目，很像貪心，采用盡可能逼近目标的貪心法來逐次合并。如樣例資料，從最上面一堆開始，沿順時針方向排成一個環，要計算得分最小時，第一次去相鄰得分最小的4,4兩堆合并，得分為8分，合并後剩下3堆，分别為8 5 9；再選擇相鄰得分最小的5,8合并，得13分，最後選9和13合并，得22分，總共分數為43，與樣例輸出一樣，好像這種貪心是正确的。

其實不然，這種政策存在反例。如6堆石子，從最上面一堆順時針數起，石子數分别為3,4,6,5,4,2，采用貪心政策合并時，合并過程如下：

但是經過反複推敲，可以得到一種總得分更小的合并方案，合并過程如圖2。

顯然，圖2的合并方案更優。樣例資料其實是一種用貪心政策可以解決問題的假象，導緻很多選手使用了貪心政策，進而丢了很多分。下面來分析第二種合并方案。從後往前推，有圖2可以看出，6堆石子合并的最小得分方案min{merge(1,2,3,4,5,6)}是由merge(1,2,3)和merge(4,5,6)得來的，上述中，merge表示合并， 1,2,3,…表示第1,2,3,…堆的石子。merge(1,2,3)時，它有兩種合并方案，即先merge(1,2)兩堆，再将1,2合并得結果與第3堆合并，merge(merge(1,2),3)；或者先merge(2,3)，然後merge(1,merge(2,3))。

第一種合并方案（3+4）+6的合并得分為7+13=20；

第二種合并方案3+（4+6）的合并得分為10+13=23。

明顯第一種方案得分少。merge(4,5,6)時，也同樣有兩種方案。合并1到6堆得過程如下：

合并1堆：1,2，…，6;

合并2堆：12,23,…,61;

合并3堆：123,234,…,612;

合并4堆：1234,2345,…,6123;

合并5堆：12345,23456,…,61234;

合并6堆：123456,234561,…,612345。

是以，從第i堆開始合并到第j堆時，它的值可以為第i堆+min{merge(i+1,i+2,…,i+j-1)}。如從第1堆開始合并4堆時，它可以為第1堆+min{merge(2,3,4)}，也可以為min{merge(1,2)+merge(3,4)}，也可以為min{merge(1,2,3)}+第4堆，共3種來源，與區間的合并有關。依次類推，合并到6堆時，去從第i堆開始合并6堆得最小值，即得到合并得總的最小值。是以，此問題具備最優子結構的性質，而且無後效性。

階段：合并得堆數。

狀态：dp[i,j]。表示從第i堆起，順時針合并j堆得總得分最小值，它包括合并前j-1堆的最小總得分加上這次合并得得分，用sum[i,j]表示這次合并得得分。合并時的堆數可以表示為序列{第i堆，第i+1堆，….，第(i+j-2) mod n+1堆}。序列總得來的方案有很多種，我們用子序列1和子序列2表示，如子序列1為{第i堆}，子序列2為{第i+1堆，…，第(i+j-2)mod n+1堆}。子序列1和子序列2相鄰，是以，假如子序列1為k堆，則子序列2為j-k堆。由此，可以得到動規方程：

dp[i,j]=min{dp[i,k]+dp[i+k,j-k]+sum[i,j] , 1≤k≤j-1}

stone[i]表示初始時每堆的石子數，則動規的初始條件為：dp[i,1]=0

動規的邊界為1≤i＜n，1≤j≤n。求最大得分與最小得分方法一樣，隻是在計算時反一下就可以了。

從石子合并得算法來看，狀态dp[i,j]與合并時的起始位置和前j-1個合并區間有關，是典型的區間型動态規劃。

#include<cstdio>

using namespace std;
const int maxn=;
int num[];
int sum[][];//這一次合并得到的分數
int fmax[][];//從第i堆石子開始，合并j堆石子得到的最大值
int fmin[][];//從第i堆石子開始，合并j堆石子得到的最小值

int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=;i<=n;++i)
    {
        scanf("%d",&num[i]);
        sum[i][]=num[i];
        fmax[i][]=;
        fmin[i][]=;
    }

    for(j=;j<=n;++j)
        for(i=;i<=n;++i)
            sum[i][j]=num[i]+sum[(i%n)+][j-];//轉一圈，相當于從誰開始合并都考慮了。

    for(j=;j<=n;++j)
    {
        for(i=;i<=n;++i)
        {
            fmax[i][j]=;
            fmin[i][j]=maxn;
            for(int k=;k<=j-;++k)
            {
                int next=((i+k-)%n)+;
                if(fmax[i][j]<sum[i][j]+fmax[next][j-k]+fmax[i][k])//序列一序列二合并也會得分而且得的分都是sum[i][j]因為加法滿足結合律。
                    fmax[i][j]=sum[i][j]+fmax[next][j-k]+fmax[i][k];
                if(fmin[i][j]>sum[i][j]+fmin[next][j-k]+fmin[i][k])
                    fmin[i][j]=sum[i][j]+fmin[next][j-k]+fmin[i][k];
            }
        }
    }
    //哪個位置當第一次合并
    int min=maxn ,max=;
    for(i=;i<=n;++i)
    {
        if(min>fmin[i][n])
            min=fmin[i][n];
        if(max<fmax[i][n])
            max=fmax[i][n];
    }
    printf("%d\n%d",min,max);
    return ;
}

           

【NOIP2000提高】乘積最大

【線上測試送出傳送門】

【問題描述】

今年是國際數學聯盟确定的“2000――世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場别開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
  設有一個長度為N的數字串，要求選手使用K個乘号将它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
  同時，為了幫助選手能夠正确了解題意，主持人還舉了如下的一個例子：
有一個數字串：312， 當N=3，K=1時會有以下兩種分法：（1） 3*12=36   （2）31*2=62
這時，符合題目要求的結果是：31*2=62
現在，請你幫助你的好朋友XZ設計一個程式，求得正确的答案。
      

【輸入格式】

程式的輸入共有兩行：
第一行共有2個自然數N，K（6≤N≤40，1≤K≤6）
第二行是一個長度為N的數字串
      

【輸出格式】

輸出共1行,1個整數，表示所求得的最大乘積。
      

【輸入樣例1】

4  2
1231
      

【輸出樣例1】

62
      

【解題思路】

從題意來看，“*”号的插入方式非常重要。比如樣例，如果插入位置為1*23*1時，結果為23；插入位置為12*3*1時，結果為36；插入位置為1*2*31時，結果為62，這種方式的值最大。從這點來看，本題與石子合并非常相像。設輸入的數字串味s，在s1,...,si(2≤i≤n)中插入j個“*”時，假設在s1,..,sk中插入了j-1個“*”号，則乘式中第j個“*”号後邊的式子sk+1,..,si為常量；設f[i,j]表示在長度為i的數字串中插入j個“*”的最大乘積，要得到f[i,j]的最大值時，就要得到max{f[k,j-1]*sk+1...sn (j≤k≤i-1)}的值；一一枚舉k的位置，即可得到max{f[k,j-1]*sk+1..sn}的值。最後輸出f[n,m]的值即可。顯然，這一問題具備最優子結構的性質，且無後效性，也是區間型動規類問題。
    階段：數字串的長度；
    狀态：長度為i的數字串中插入的“*”的個數；
    決策：第j個“*”的最佳插入位置。
      

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=;
int n,K;
string s;
int a[maxn];
struct lxt
{
    int len;
    int ans[maxn];
}dp[maxn/][maxn];

lxt cal(lxt x,int l,int r)
{
    lxt Ans,y;
    memset(Ans.ans,,sizeof(Ans.ans));
    memset(y.ans,,sizeof(y.ans));
    y.len=r-l+;
    for(int i=r;i>=l;--i) y.ans[r-i+]=a[i];
    int l1=x.len,l2=y.len,ll;
    for(int i=;i<=l1;++i)
      for(int j=;j<=l2;++j)
          Ans.ans[i+j-]+=x.ans[i]*y.ans[j];
    ll=l1+l2-;      
    for(int i=;i<=ll;++i)
    {
        Ans.ans[i+]+=Ans.ans[i]/;
        Ans.ans[i]=Ans.ans[i]%;
    }
    if(Ans.ans[ll+]) ll++;
    Ans.len=ll;
    return Ans;
}
lxt cmp(lxt x,lxt y)
{
    int lx=x.len,ly=y.len;
    if(lx<ly) return y;
    if(lx>ly) return x;
    for(int i=lx;i>=;--i)
    {
        if(x.ans[i]>y.ans[i]) return x;
        if(x.ans[i]<y.ans[i]) return y;
    }
    return x; 
}
int main()
{
    scanf("%d%d",&n,&K);
    cin>>s;
    for(int i=;i<=n;++i) a[i]=s[i-]-'0';
    for(int i=;i<=n;++i)
      for(int j=i;j>=;--j)
        dp[][i].ans[++dp[][i].len]=a[j];
    for(int i=;i<=n;++i)
      for(int k=;k<=min(K,i-);++k)
        for(int j=k;j<i;++j)
          dp[k][i]=cmp(dp[k][i],cal(dp[k-][j],j+,i));
    for(int i=dp[K][n].len;i>=;--i)
      printf("%d",dp[K][n].ans[i]);
    return ;
}
           

【NOIP2006提高組】能量項鍊

【線上測試送出傳送門】

【問題描述】

在Mars星球上，每個Mars人都随身佩帶着一串能量項鍊。在項鍊上有N顆能量珠。能量珠是一顆有頭标記與尾标記的珠子，這些标記對應着某個正整數。并且，對于相鄰的兩顆珠子，前一顆珠子的尾标記一定等于後一顆珠子的頭标記。因為隻有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭标記為m，尾标記為r，後一顆能量珠的頭标記為r，尾标記為n，則聚合後釋放的能量為m*r*n（Mars機關），新産生的珠子的頭标記為m，尾标記為n。
    需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鍊上隻剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鍊釋放出的總能量最大。
    例如：設N=4，4顆珠子的頭标記與尾标記依次為(2，3) (3，5) (5，10) (10，2)。我們用記号⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合後所釋放的能量。則第4、1兩顆珠子聚合後釋放的能量為：(4⊕1)=10*2*3=60。
這一串項鍊可以得到最優值的一個聚合順序所釋放的總能量為((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
      

【輸入格式】

輸入檔案的第一行是一個正整數N（4≤N≤100），表示項鍊上珠子的個數。
第二行是N個用空格隔開的正整數，所有的數均不超過1000。第i個數為第i顆珠子的頭标記（1≤i≤N），當1≤i＜N時，第i顆珠子的尾标記應該等于第i+1顆珠子的頭标記。第N顆珠子的尾标記應該等于第1顆珠子的頭标記。
至于珠子的順序，你可以這樣确定：将項鍊放到桌面上，不要出現交叉，随意指定第一顆珠子，然後按順時針方向确定其他珠子的順序。
      

【輸出格式】

輸出隻有一行，是一個正整數E（E≤2.1*10^9），為一個最優聚合順序所釋放的總能量。
      

【輸入樣例1】

4
2 3 5 10
      

【輸出樣例1】

710
      

【解題思路】

用head表示第i顆珠子的頭标記，用tail表示尾标記，合并兩顆相鄰珠子所釋放的能量為：energy=head[i]*tail[i]*tail[i+1]

合并時不一定按輸入順序合并，與石子合并問題類似，第n次合并，可以歸結到第n-1次合并，具有明顯地動規性質。用f[I,j]表示從第i顆珠子合并到第j顆珠子時産生的最大能量，用k表示最後一次的合并位置，則有： dp[i,j]=max{dp[i,k]+dp[k+1,j]+head[i]*tail[k]*tail[j] , i≤k≤j} 上式中，dp[i,k]表示第i顆到第k顆珠子産生的最大能量，dp[k+1,j]表示合并第k+1顆到第j顆時産生的最大能量，head[i]*tail[k]*tail[j]表示最後一次合并時産生的能量。dp[i,j]的值，分成兩個區間，取最大值，是典型的區間型動規。最後一次合并時，産生的能量為什麼是head[i]*tail[k]*tail[j]呢？假設有5顆珠子，每顆珠子的能量為10,2,3,5,6，當i=1,j=4,k=2時，如圖：

由圖可以看出，合并dp[1,2]，dp[3,4]後，還剩下1,3,5三顆珠子（從最上面開始順時針數），此時1号珠子head[1]=10，tail[1]=3，相當于原圖的tail[2]；3号珠子tail[3]=6，相當于原圖的tail[4]。最後合并dp[1,4]時，相當于合并1,3兩顆珠子，産生的能量為最右邊圖的10*3*6，相當于原圖中的head[1]*tail[2]*tail[4]，即為上式中的head[i]*tail[k]*tail[j]。

由于項鍊是一個環，我們把項鍊以2*n-1長度，一水準線的形式平鋪在桌面上，從左到右逐一掃描，得出最大值。

實作：

重點就是将整體劃分為區間，小區間之間合并獲得大區間

狀态轉移方程的推導如下

一、将珠子劃分為兩個珠子一個區間時，這個區間的能量=左邊珠子*右邊珠子*右邊珠子的下一個珠子

二、區間包含3個珠子，可以是左邊單個珠子的區間+右邊兩珠子的區間，或者左邊兩珠子的區間右邊+單個珠子的區間

即，先合并兩個珠子的區間，釋放能量，加上單個珠子區間的能量（單個珠子沒有能量。。）

Energy=max(兩個珠子的區間的能量+單個珠子區間的能量，單個珠子的區間的能量+兩個珠子的區間的能量 ）

三、繼續推4個珠子的區間，5個珠子的區間。

于是可以得到方程：Energy=max（不操作的能量，左區間合并後的能量+右區間合并後的能量+兩區間合并産生能量）

兩區間合并後産生的能量=左區間第一個珠子右區間第一個珠子總區間後面的一個珠子

#include<bits/stdc++.h>
using namespace std;
int n,e[],s[][],maxn=-;
int main(){
    cin>>n;
    for(int i=;i<=n;i++){cin>>e[i];e[i+n]=e[i];}
    //珠子由環拆分為鍊，重複存儲一遍
    for(int i=;i<*n;i++){
        for(int j=i-;i-j<n&&j>=;j--){//從i開始向前推
            for(int k=j;k<i;k++)//k是項鍊的左右區間的劃分點 
            s[j][i]=max(s[j][i],s[j][k]+s[k+][i]+e[j]*e[k+]*e[i+]);
            //狀态轉移方程：max(原來能量，左區間能量+右區間能量+合并後生成能量）  
            if(s[j][i]>maxn)maxn=s[j][i];//求最大值 
        }
    } 
    cout<<maxn;
    return ;
}
           

【洛谷1622】釋放囚犯

【線上測試送出傳送門】

【問題描述】

Caima王國中有一個奇怪的監獄，這個監獄一共有P個牢房，這些牢房一字排開，第i個緊挨着第i+1個（最後一個除外）。現在正好牢房是滿的。
  上級下發了一個釋放名單，要求每天釋放名單上的一個人。這可把看守們吓得不輕，因為看守們知道，現在牢房中的P個人，可以互相之間傳話。如果某個人離開了，那麼原來和這個人能說上話的人，都會很氣憤，導緻他們那天會一直大吼大叫，搞得看守很頭疼。如果給這些要發火的人吃上肉，他們就會安靜點。
      

【輸入格式】

第一行兩個數P和Q，Q表示釋放名單上的人數；
第二行Q個數，表示要釋放哪些人。
      

【輸出格式】

僅一行，表示最少要給多少人次送肉吃。
      

【輸入樣例1】

20 3
3 6 14
      

【輸出樣例1】

35
      

【樣例說明】

先釋放14号監獄中的罪犯，要給1到13号監獄和15到20号監獄中的19人送肉吃；再釋放6号監獄中的罪犯，要給1到5号監獄和7到13号監獄中的12人送肉吃；最後釋放3号監獄中的罪犯，要給1到2号監獄和4到5号監獄中的4人送肉吃。
      

【資料範圍】

對于50%的資料 1≤P≤100；1≤Q≤5
對于100%的資料1≤P≤1000； 1≤Q≤100；Q≤P；
      

【解題思路】

把要釋放的人視作斷點，将p個人分成q+1個區間，求合并區間至一個區間所需最小值，即可視為合并石子。
 注意分成q+1個區間時的一些細節。
      

#include<bits/stdc++.h>  
using namespace std;  
int s[][]={},p,q,a[]={},sum[]={};  
inline void init()  
{  
    scanf("%d%d",&p,&q);  
    for(int i=;i<=q;i++)scanf("%d",&a[i]);  
    a[]=;a[++q]=p+;  
    sort(a,a+q+);  
    return;  
}  

int main()  
{  
    init();  
    for(int i=;i<=q;i++)  
    sum[i]=a[i]-a[i-]-+sum[i-];//字首和，将問題轉換為求幾堆石子合并的最小值  
    for(int k=;k<=q;k++)  
    for(int i=;i<=q-k+;i++)  
    {  
        int j=i+k-;  
        for(int p=i;p<j;p++)  
        if(!s[i][j]||s[i][j]>s[i][p]+s[p+][j]+sum[j]-sum[i-]+j-i-)//注意j-i+1，是指合并時幾個還未釋放的人所需的代價
        s[i][j]=s[i][p]+s[p+][j]+sum[j]-sum[i-]+j-i-;  
    }  
    printf("%d",s[][q]);  
    return ;  
}  
           

【洛谷2858】奶牛零食

【線上測試送出傳送門】

【問題描述】

約翰經常給産奶量高的奶牛發特殊津貼，于是很快奶牛們擁有了大筆不知該怎麼花的錢．為此，約翰購置了N(1≤N≤2000)份美味的零食來賣給奶牛們．每天約翰售出一份零食．當然約翰希望這些零食全部售出後能得到最大的收益．這些零食有以下這些有趣的特性：
    1.零食按照1..N編号，它們被排成一列放在一個很長的盒子裡．盒子的兩端都有開口，約翰每天可以從盒子的任一端取出最外面的一個；
    2.與美酒與好吃的奶酪相似，這些零食儲存得越久就越好吃．當然，這樣約翰就可以把它們賣出更高的價錢；
    3.每份零食的初始價值不一定相同．約翰進貨時，第i份零食的初始價值為Vi(1≤Vi≤1000)；
    4.第i份零食如果在被買進後的第a天出售，則它的售價是vi×a。Vi指的是從盒子頂端往下的第i份零食的初始價值。
約翰告訴了你所有零食的初始價值，并希望你能幫他計算一下，在這些零食全被賣出後，他最多能得到多少錢。
      

【輸入格式】

第一行，一個整數n；
接下來n行，每行一個整數表示Vi。
      

【輸出格式】

一行，一個整數，表示最多的錢。
      

【輸入樣例1】

5
1
3
1
5
2
      

【輸出樣例1】

43
      

【解題思路】

dp[i][j]=max(dp[i+1][j]+a[i]*(n-l+1),dp[i][j-1]+a[j]*(n-l+1));//有兩種情況一種是選開頭點的那一個最優,一種是選結束點的那一個最優
      

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<algorithm>
#include<fstream>
using namespace std;
int dp[][],a[];
int main(){
    int n,l,i,j;
    cin>>n;
    for(i=;i<=n;i++){
        cin>>a[i];
        dp[i][i]=a[i]*n;//初始化:将區間長度為1的情況指派為最後一個拿(n*a[i])
    }
    for(l=;l<=n;l++){//枚舉長度
        for(i=;(i+l-)<=n;i++){//枚舉開頭點,注意範圍(開頭點加長度減一不超過總長度)
            j=i+l-;//推出結束點
            dp[i][j]=max(dp[i+][j]+a[i]*(n-l+),dp[i][j-]+a[j]*(n-l+));//有兩種情況一種是選開頭點的那一個最優,一種是選結束點的那一個最優
        }
    }
    cout<<dp[][n]<<endl;//最後直接輸出從開頭到末尾的最大值
    return ;
}
           

//記憶化搜尋寫法：
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    int n,a[],f[][],ans;
    //其中f數組表示在l,r區間中的最大值，a數組為讀入//的數組，ans用來存儲最後值（不用也行）
    int dfs(int k,int l,int r)//記憶化開始
    //k代表已經賣掉了幾個零食（也可表示為層次）
    {
        int p=;
        if (k>n) return ;//邊界
        if (f[l][r]!=-) return f[l][r];
        //如果已經搜尋過，則不需要再次搜尋，return
        if (l>r) return ;//邊界
        p=max(p,dfs(k+,l+,r)+a[l]*k);//計算
        p=max(p,dfs(k+,l,r-)+a[r]*k);//計算
        f[l][r]=p;//存儲目前最優解
        return p;
    }
    int main()
    {
        scanf("%d",&n);
        for (int i=;i<=n;i++)
        for (int j=;j<=n;j++)
        f[i][j]=-; //賦初值标記是否搜尋過
        for (int i=;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        ans=dfs(,,n);//記憶化
        printf("%d",ans);
    } 
           

【POJ1141】Brackets Sequence 括号比對

【線上測試送出傳送門】

【問題描述】

定義正确的括号序列為：
1.空序列是一個正确的括号序列；
2.如果S是一個正确的括号序列，那麼(S)和[S]也是正确的括号序列；
3.如果A和B是正确的括号序列，那麼AB也是正确的括号序列。
例如，正确的括号序列有：(), [], (()), ([]), ()[], ()[()] 
例如，不正确的括号序列：(, [, ), )(, ([)], ([(] 
現在給定一個括号序列，需要你添加最少的括号，是的該括号序列是一個正确的括号序列。
      

【輸入格式】

一行，一個括号序列，不超過100個符号。
      

【輸出格式】

一行，一個正确的括号序列。
      

【輸入樣例1】

([(]
      

【輸出樣例1】

()[()]
      

【解題思路】

d[i][j]表示從i到j的範圍内最少需要添加的括号數
pos[i][j]表示i到j的範圍内從pos[i][j]處分開進行添加可使得括号數最小，為-1表示無需分開添加
若s[i]和s[j]組合為"()"或"[]",則說明已經配對，隻需處理i和j内部的序列，且暫時令pos[i][j]=-1；
然後枚舉i到j中的分界點，檢視是否存在k使得d[i][j]＞d[i][k]+d[k][j]（狀态轉移方程），若存在，
則說明将i和j從k處分離成兩部分進行處理可使得添加的括号數更小，此時令pos[i][j]=k，記錄下此分界點

show函數說明：利用遞歸輸出比對後的括号序列
1、如果i＞j，越界，則傳回
2、如果i==j，說明隻處理的一個括号，輸出對應的配對括号對即可
3、如果i＜j，首先判斷pos[i][j]?-1，若相等，說明i和j之間無需分解，
先輸出左邊，然後遞歸輸出中間，最後輸出右邊括号；若不相等，則遞歸
輸出i到pos[i][j]，pos[i][j]+1到j兩部分
      

#include<iostream>
using namespace std;
#define N 105
#define INF 1e9
int d[N][N];
int pos[N][N];
char s[N];  //接受初始資料
void Match(int len)
{
 int i,j,k;
 for(i=;i<len;i++)
  d[i][i]=;
 for(k=;k<len;k++)   //表示i和j之間的間隔
  for(i=;i<len-k;i++)
  {
   char right=s[i+k];
   char left=s[i];
   d[i][i+k]=INF;  //此條語句不能少，假如下面的if不執行，則for中判斷就會出錯d[i][i+k]未指派
   if(left=='('&&right==')'||left=='['&&right==']')
   {
    d[i][i+k]=d[i+][i+k-];
    pos[i][i+k]=-;
   }
   for(j=i;j<i+k;j++) //靠左分界
    if(d[i][i+k]>d[i][j]+d[j+][i+k])
    {
     pos[i][i+k]=j;
     d[i][i+k]=d[i][j]+d[j+][i+k];
    }
  }
}
void show(int i,int j)
{
 if(i>j)  return;
 if(i==j)
 {
  if(s[i]=='('||s[i]==')') cout<<"()";
  else      cout<<"[]";
 }
 else
 {
  if(pos[i][j]==-)
  {
   cout<<s[i];
   show(i+,j-);
   cout<<s[j];
  }
  else
  {
   show(i,pos[i][j]);
   show(pos[i][j]+,j);
  }
 }
}
int main()
{  
 cin>>s;
 int len=strlen(s);
 Match(len);
 show(,len-);
 cout<<endl;
 return ;
}
           

【HDU4745】Two Rabbits

【線上測試送出傳送門】

【問題描述】

有兩隻兔子Tom和Jerry，他們在玩一個遊戲。n塊石頭圍成一圈，編号依次為1到n，第1塊石頭和第2塊石頭、第n塊石頭相鄰。第i塊石頭的重量是ai。
  兔子可以從一塊石頭跳到另外一塊石頭上，Tom順時針跳，Jerry逆時間跳。
  開始時，他們可以選擇一塊石頭，站在上面，每一輪，Tom選擇跳到一塊他自己沒有跳上去過的石頭，Jerry也是一樣，隻是方向不同。
  在每一個時間，兩隻兔子所站的石頭的重量必須相同。而且跳的時候，不能越過已經跳過的石頭。例如，如果Tom已經跳到過第2塊石頭，他就不能從第1塊石頭跳到第3塊石頭，或者從第n塊石頭跳到第4塊石頭。
  遊戲過程中，Tom和Jerry可以同時站在同一塊石頭上。
  請計算，他們最多可以進行多少輪遊戲。
      

【輸入格式】

輸入最多包含20組測試資料，對于每組測試資料：
第一行，一個整數n，表示石頭的數量；
第二行，n個整數，依次表示每一塊石頭的重量ai；
當n=0時，表示輸入結束。
      

【輸出格式】

對于每組測試資料輸出一行一個整數，表示最多的遊戲輪數。
      

【輸入樣例1】

1
1
4
1 1 2 1
6
2 1 1 2 1 3
0
      

【輸出樣例1】

1
4
5
      

【樣例解釋】

對于第2個樣例，Tom的序列是1,2,3,4；Jerry的序列是1,4,3,2;
對于第3個樣例，Tom的序列是1,2,3,4,5；Jerry的序列是4,3,2,1,5。
      

【資料範圍】

1 ≤ n ≤ 1000, 1 ≤ ai ≤ 1000
      

【解題思路】

區間DP, 轉換成求最長非連續的回文串
将數組擴大為2倍,計算每個區間的最長非連續的回文串
狀态轉移方程dp[i][j] = max(dp[i][j], dp[i+1][j], dp[i][j-1], a[i]==a[j]?a[i+1][j-1]+2:0)
注意像字元串1221,計算出來的dp[0][3] = 4,而不是2
是以最後結果肯定是隻有n個字元,或者n-1的字元加個1
      

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 1005
#define inf 0x3f3f3f3f
using namespace std;

int a[maxn<<];
int dp[maxn<<][maxn<<];          //dp[i][j] 表示區間[i,j]的最長非連續的回文串

int main()
{
    int n;
    while(scanf("%d", &n),n)
    {
        memset(dp, , sizeof(dp));
        for(int i=; i<n; i++)
        {
            scanf("%d", &a[i]);
            a[n+i] = a[i];
        }
        //1個字元時,肯定是1了
        for(int i=; i<*n; i++)
            dp[i][i] = ;
        for(int len=; len<=*n; len++)
            for(int i=; i+len<*n; i++)
            {
                int j = i+len-;
                if(a[i]==a[j])
                {
                    dp[i][j] = max(dp[i][j], dp[i+][j-]+);
                }
                dp[i][j] = max(dp[i][j], max(dp[i+][j], dp[i][j-]));
            }
        int ans = ;
        //n個字元
        for(int i=; i<n; i++)
            ans = max(ans, dp[i][i+n-]);
        //n-1個字元,最後一個當做公共的起點,是以+1
        for(int i=; i<n; i++)
            ans = max(ans, dp[i][i+n-]+);
        printf("%d\n", ans);
    }
    return ;
}