區間DP(石子合并及同類題)

石子合并1
題意：一條直線上擺放著一行共n堆的石子，現要將石子有序地合并成一堆，規定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆石子數記為該次合并的得分，請編輯計算出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分，

還是比較好理解的，我們先求出n堆石子的前綴和，這樣我們求新合成的一堆石子數只需要知道這堆石子的前后位置作差即可，再考慮怎么合成，我們首先構造二維陣列DP[i][j]表示從第i位置到第j位置為新合成的一堆石子的得分，DP[i][j]的合成方式有多種，可以是DP[i][i]+DP[i+1][j]，DP[i][i+1]+DP[i+2][j]，……DP[i][j-1]+DP[j][j]這些情況用一個通式dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]｛i<=k<j}表示，前半部分表示不同的合成方式，后面的sum[j]-sum[i-1]是從第i位置到第j位置新合成的這一堆石子的個數(得分)，k的范圍一定要弄清楚，可以等于i表示由第i個與第i+1到j這一大個合成的；不等于j，當k=j-1時，表示由第i到j-1這一大個與第j個合成的，這為最后一種合成情況，
再在每種情況里取最小值與最大值即可，

注意：由于DP[i][j]的值的確定是多種方式中取的最優，所以我們需要將每一次的結果都與DP[i][j]比較，需要對其賦初始值以保證第一次的結果正確，求最小得分我們對其賦大值，最大得分賦0即可，注意賦的大值不是隨便賦一個數，過大的數會使其資料溢位，不算太大的數會使其結果錯誤，總結發現，對一個整形變數我們對其賦值0x3f3f3f3f較好，陣列初始化memset(dp,0x3f,sizeof(dp))較好，資料不溢位且答案正確
詳細解釋

#include<iostream>
#include<cstring>
using namespace std;
int a[205],sum[205]= {0},dn[205][205],dx[205][205];
int main()
{   int n,i,j,k;
    int minn=0x3f3f3f3f,maxx=-1;
    while(cin>>n)
    {   minn=0x3f3f3f3f,maxx=-1;
        memset(dx,0,sizeof(dx));
        memset(dn,0x3f,sizeof(dn));
        for(i=1; i<=n; i++)
        {   cin>>a[i];
            sum[i]=sum[i-1]+a[i];//計算前綴和
            dn[i][i]=0;//一個石子，沒有合成時，初始條件是0
        }
        for(int len=2; len<=n; len++)//長度從2開始，表示由兩個石子合并成一個
        {
            for(i=1; i+len-1<=n; i++)//i+len-1為區間的右端點j
            {
                j=i+len-1;
                for(k=i; k<j; k++)
                {   
                    dn[i][j]=min(dn[i][j],dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]);
                    dx[i][j]=max(dx[i][j],dx[i][k]+dx[k+1][j]+sum[j]-sum[i-1]);

                }
            }
        }
        cout<<dn[1][n]<<" "<<dx[1][n]<<endl;
    }
    return 0;
}

石子合并2
題意：在圓形操場上擺放著一行共n堆的石子，現要將石子有序地合并成一堆，規定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆石子數記為該次合并的得分，請編輯計算出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分，

這個題和上一個題的區別是圓形范圍，情況變多了，因為是一個環，最后一個可以和第一個和并，
也就是考慮的范圍應該是1 2 3 4 5 6 1 2 3 4 5 6，即2*n，處理方式與上面相同，但最后需要比較從不同位置開始的長度為n（說明n個石子合并成了一個，只是合成的起始位置不同）的石子個數的結果

#include<iostream>
#include<cstring>
using namespace std;
int a[205],sum[205],dn[205][205],dx[205][205];
int main()
{
    int n,i,j,k,minn=0x3f3f3f3f,maxx=-1;
    while(cin>>n)
    {   minn=0x3f3f3f3f,maxx=-1;
        memset(dx,0,sizeof(dx));
        memset(dn,0x3f,sizeof(dn));
        for(i=1; i<=n; i++)
        {   cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            dn[i][i]=0;
        }
        for(i=n+1; i<=2*n; i++)
        {   sum[i]=sum[i-1]+a[i-n];
            dn[i][i]=0;
        }
        for(int len=2; len<=n; len++)
        {
            for(i=1; i+len-1<=2*n; i++)
            {
                j=i+len-1;
                for(k=i; k<j; k++)
                {   
                    dn[i][j]=min(dn[i][j],dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]);
                    dx[i][j]=max(dx[i][j],dx[i][k]+dx[k+1][j]+sum[j]-sum[i-1]);

                }
            }
        }
        for(i=1; i<=n; i++)
        {
            minn=min(minn,dn[i][i+n-1]);//比較不同位置開始的情況
            maxx=max(maxx,dx[i][i+n-1]);
        }
        cout<<minn<<" "<<maxx<<endl;
    }
    return 0;
}

P
題意：給你一串珠子，如果前一顆能量珠的頭標記為m，尾標記為r，后一顆能量珠的頭標記為r，尾標記為n，則聚合后釋放的能量為mrn，新產生的珠子的頭標記為m，尾標記為n，問只剩下一顆珠子使這串珠子釋放的總能量最大，

這個問題類似于石子合并問題2，動態轉移方程中前半部分珠串合成方式和石子合并一樣為dp[i][k]+dp[k+1][j]，后面總能量單獨求，由于每次合成一個新的珠子時，它的頭標記和尾標記的值變化，發現頭標記m的值就是前一部分dp[i][k]中首位置對應的值即a[i]，尾標記n的值為后一部分dp[k+1][j]的尾位置的下一位，即a[j+1]，畫個圖理解，以2 3 5 10為例

黑色的表示數字的位置，由圖可知，r的值為a[k+1]
所以動態轉移方程為dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])

#include<iostream>
#include<cstring>
using namespace std;
int a[205],d[205][205];
int n,i,j,k;
int main()
{
    while(cin>>n)
    {   int maxx=-1;
        memset(d,0,sizeof(d));
        for(i=1; i<=n; i++)
        {   cin>>a[i];
            a[i+n]=a[i];
        }
        for(int len=2;len<=n;len++)
        {
            for(i=1,j=len; j<=2*n; i++,j++)
            {
                for(k=i; k<j; k++)
                {
                    d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]);
                }
            }
        }
        for(i=1; i<=n; i++)
        {
            maxx=max(maxx,d[i][i+n-1]);
        }
        cout<<maxx<<endl;
    }
    return 0;
}

C
題意：給你一行牌，每一張牌包括了一個正整數，在每一個移動中，玩家拿出一張牌，得分是用它的數字乘以它左邊和右邊的數，不允許拿第1張和最后1張牌，最后一次移動后，只剩下兩張牌，你的目標是使得分的和最小，

這個題和上面合成珠子的題和石子合并1都很像，處理方式仿造石子合并1，dp[i][j]表示i到j區間里的得分和，倒著看這個題，我們把取數看成添數，即在i，j之間加k，然后下一個數字加到ik中間或者kj中間，依次類推，這里的i和j就相當于第一張牌和最后一張牌，不取，k和其他數是要取的牌，所以可以構建動態轉移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j](i<=k<j)，怎么對陣列初始化呢，舉個例子理解，如果i=1,j=2時，1和2為邊界，不取，當k等于i時，dp[i][i]讓它無窮大，同時dp[i][j]也要無窮大，因為我們最終要的是最小值，我們一開始可以對陣列初始化讓它無窮大，以上i=1，j=2的那種情況滿足，如果i=1,j=3，1和3為邊界不取，考慮k=2的情況，因為a[1]*a[2]*a[3]即為結果，所以要對dp[1][2]和dp[2][3]賦0，其他區間同樣，所以需要對dp[i][i+1]賦0，

#include<iostream>
#include<cstring>
using namespace std;
int a[205],d[205][205];
int n,i,j,k;
int main()
{
    while(cin>>n)
    {   int minn=0x3f3f3f3f;
        memset(d,0x3f,sizeof(d));
        for(i=1; i<=n; i++)
        {   cin>>a[i];
            d[i][i+1]=0;
        }
        for(int len=2;len<=n;len++)
        {
            for(i=1,j=len; j<=n; i++,j++)
            {
                for(k=i; k<j; k++)
                {
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]+a[i]*a[k]*a[j]);
                }
            }
        }
        cout<<d[1][n]<<endl;
    }
    return 0;
}