区间DP训练

一、石子合并

问题描述
- 将 n (\(1 \le n \le 200\))堆石子绕圆形操场摆放，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。请编一程序，由文件读入读入堆数 n 及每堆的石子数。① 选择一种合并石子的方案，使得做 n -1 次合并，得分的总和最小。② 选择一种合并石子的方案，使得做 n -1 次合并，得分的总和最大。
输入格式
- 输入第一行为一个整数 n ，表示有 n 堆石子，第二行为 n 个整数，分别表示每堆石子的数量。
输出格式
- 输出共 2 行，第一行为合并得分总和最小值，第二行为合并得分总和最大值。
样例输入
```
4

4 5 9 4
```
样例输出
```
43

54
```

代码

#include <cstdio>

#include <iostream>

using namespace std;

const int maxn = 205,MAX = 0x7fffffff/2;

int f1[maxn][maxn],f2[maxn][maxn],s[maxn][maxn] = {0};

int a[maxn],sum[maxn] = {0},n,i,ans1,ans2;

void init();

void dp();

int main()

{

    init();

    dp();

    printf("%d\n%d\n",ans1,ans2);

    return 0;

}

void init()

{

    scanf("%d",&n);

    for(i = 1; i <= n; i++)

    {

        scanf("%d",&a[i]);

        a[i+n] = a[i];

    }

    for(i = 1; i <= n*2; i++)

    {

        sum[i] = sum[i-1] + a[i];

        f2[i][i] = 0;

        f1[i][i] = 0;

    }

}

void dp()

{

    int j,k,L;

    for(L = 2; L <= n; L++)

        for(i = 1; i <= 2*n-L+1; i++)

        {

            j = i+L-1;

            f1[i][j] = 0xfffffff/2;

            f2[i][j] = 0;

            for(k = i;k < j;k++)

            {

                f1[i][j] = min(f1[i][j],f1[i][k] + f1[k+1][j]);

                f2[i][j] = max(f2[i][j],f2[i][k] + f2[k+1][j]);

            }

            f1[i][j] += sum[j] - sum[i-1];

            f2[i][j] += sum[j] - sum[i-1];

        }

        ans1 = 0x7fffffff/2,ans2 = 0;

        for(i = 1;i <= n;i++)

            ans1 = min(ans1,f1[i][i+n-1]);

        for(i = 1;i <= n;i++)

            ans2 = max(ans2,f2[i][i+n-1]);

}

二、能量项链

问题描述
- 在 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)。我们用记号 \(\oplus\) 表示两颗珠子的聚合操作，\((j \oplus k)\) 表示第 j，k 两颗珠子聚合后所释放的能量。则第4，1 两颗珠子聚合后释放的能量为：\((4\oplus1) = 10×2×3 = 60\)。这一串项链可以得到最优价值的一个聚合顺序所释放的总能量为：\(((4\oplus1)\oplus2)\oplus3 = 10×2×3+10×3×5+10×5×10 = 710\)。
输入文件
- 输入文件的第一行是一个正整数 N(\(4\le N \le 100\))，表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数，所有的的数均不超过 1000 。第 i 个数为第 i 颗珠子的头标记(\(1 \le i \le N\))，当 \(i<N\) 时，第 i 颗珠子的尾标记应该等于第 i + 1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。
- 至于珠子的顺序，你可以这样确定：将项链放在桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序
输出格式
- 输出文件只有一行，是一个正整数 E(\(R \le 2.1×10^9\))，为一个最优聚合顺序所释放的总能量
样例输入
```
4

2 3 5 10
```
样例输出
```
710
```

代码

#include <cstdio>

#include <iostream>

using namespace std;

int head[205],tail[205],f[205][205] = {0};

int main()

{

    int ans = 0,n,i,t,j,k;

    scanf("%d",&n);

    for(i = 1; i <= n; i++)

    {

        scanf("%d",&head[i]);

        head[i+n] = head[i];

    }

    for(i = 1; i <= 2*n-1; i++)

        tail[i] = head[i+1];       //环变成链

    tail[2*n] = head[1];           //求尾标记

    for(i = 1; i <= 2*n-1; i++)   //初始化

        f[i][i] = 0;

    for(t = 1; t <= n-1; t++)   //阶段，合并次数

        for(i = 1; i <= 2*n-t; i++)    //状态，起始位置

        {

            j = i+t;                    //计算结束位置

            for(k = i; k <= j-1; k++)     //决策

                f[i][j] = max(f[i][j],f[i][k] + f[k+1][j] + head[i]*tail[k]*tail[j]);

        }

    for(i = 1; i <= n; i++)

        ans = max(ans,f[i][i+n-1]);                        //求出最值

    printf("%d",ans);

    return 0;

}

三、凸多边形的划分

问题描述
- 给定一个具有 N (\(N\le 50\)) 个顶点(从 1 到 N 编号)的凸多边形，每个顶点的权均是一个正整数。问：如何把这个凸多边形划分成 N - 2 个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？
输入格式
- 输入文件的第一行为顶点数 N，第二行为 N 个顶点(从 1 到 N )的权值
输出格式
- 只有一行，为这些三角形顶点的权的乘积之和的最小值
输入样例
```
5

122 123 245 231 121
```
输出样例
```
12214884
```

代码

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long int ll;

ll F[110][110][110],a[110];

ll s1[110],s2[110],s3[110];

int n;

void Mark(ll c[])

{

    for(int i = 1; i <= c[0]; i++)

    {

        c[i+1] += c[i]/10000;

        c[i] %= 10000;

    }

    while(c[c[0]+1])

    {

        c[0]++;

        c[c[0]+1] += c[c[0]]/10000;

        c[c[0]] %= 10000;

    }

}

void Mul(ll a1,ll a2,ll a3,ll c[])

{

    c[0] = c[1] = 1;

    for(int i = 1; i <= c[0]; i++)

        c[i] *= a1;

    Mark(c);

    for(int i = 1; i <= c[0]; i++)

        c[i] *= a2;

    Mark(c);

    for(int i = 1; i <= c[0]; i++)

        c[i] *= a3;

    Mark(c);

}

void Add(ll a[],ll b[],ll c[])

{

    if(a[0] > b[0])

        c[0] = a[0];

    else

        c[0] = b[0];

    for(int i = 1; i <= c[0]; i++)

        c[i] = a[i] + b[i];

    Mark(c);

}

int Compare(ll a[],ll b[])

{

    if(a[0] < b[0])

        return 0;

    if(a[0] > b[0])

        return 1;

    for(int i = a[0]; i >= 1; i--)

        if(a[i] < b[i])

            return 0;

        else if(a[i] > b[i])

            return 1;

    return 0;

}

void Print()

{

    int i;

    printf("%lld",F[1][n][F[1][n][0]]);

    for(i = F[1][n][0] - 1; i >= 1; i--)

    {

        printf("%lld",F[1][n][i]/1000);

        printf("%lld",F[1][n][i]/100%10);

        printf("%lld",F[1][n][i]/10%10);

        printf("%lld",F[1][n][i]%10);

    }

    printf("\n");

}

int main()

{

    int i,j,k,t;

    scanf("%d",&n);

    for(i = 1; i <= n; i++)

        cin>>a[i];

    for(i = 1; i <= n; i++)

        for(j = 1; j <= n; j++)

            F[i][j][0] = 0;

    for(t = 2; t <= n-1; t++)

        for(i = 1; i <= n-t; i++)

        {

            j = i+t;

            F[i][j][0] = 60;

            for(k = i+1; k <= j-1; k++)

            {

                memset(s1,0,sizeof(s1));

                memset(s2,0,sizeof(s2));

                memset(s3,0,sizeof(s3));

                Mul(a[i],a[k],a[j],s1);

                Add(F[i][k],F[k][j],s2);

                Add(s1,s2,s3);

                if(Compare(F[i][j],s3))

                    memcpy(F[i][j],s3,sizeof(s3));

            }

        }

    Print();

    return 0;

}

巴特西

区间DP训练

一、石子合并

二、能量项链

三、凸多边形的划分

最新文章

热门文章