nyoj737石子合并【区间dp】

98 阅读 0 评论 65 点赞

我是靠谱客的博主危机枫叶，这篇文章主要介绍nyoj737石子合并【区间dp】，现在分享给大家，希望可以做个参考。

和论文题不一样啊啊啊啊啊啊，这个题排一排，论文是一圈啊啊啊，WA了好久才发现

论文题最后求完数组还要找[1,n] [2,n+1].............[n,n+n+1]的最值，这个题只需要输出头一个

这个题有一个特别让我纠结的点：每个区间分成两段，但是后一半的值还没有遍历到呢，怎么办？所以第一层循环是区间长度，第二层循环是区间开头，第三层循环是区间中点。看来dp关键也不只是把状态转移方程写出来。

复制代码

/******************
nyoj737
2016.2.18
732 	868 	C/C++	02-18 15:47:11
******************/
#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;
int f[403][403],n,num[403],t[403];
void init()
{
    t[0]=0;
    for(int i=1;i<=2*n-1;i++)t[i]=t[i-1]+num[i];
}
void cal()
{
    memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=2*n-1;i++) f[i][i]=0;
    for(int k=1;k<n;k++)//length
        for(int i=1;i<=n;i++)//start
            for(int j=i;j<i+k;j++)//mid
            {
                f[i][i+k]=min(f[i][i+k],f[i][j]+f[j+1][i+k]+t[i+k]-t[i-1]);
            }
    //for(int i=1;i<=n;i++)for(int j=i+1;j<=i+n-1;j++) printf("i=%d,j=%d,f=%4dtt",i,j,f[i][j]);
}
int main()
{
    //freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);
        for(int i=n+1;i<=2*n;i++) num[i]=num[i-n];
      //  for(int i=1;i<=2*n-1;i++) printf("i=%d,num=%dn",i,num[i]);
        init();
        cal();
        int maxn=0x3f3f3f3f;
      //  for(int i=1;i<=n;i++) printf("i=%d,j=%d,f=%dn",i,i+n-1,f[i][i+n-1]);
        printf("%dn",f[1][n]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/******************
nyoj737
2016.2.18
732 	868 	C/C++	02-18 15:47:11
******************/
#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;
int f[403][403],n,num[403],t[403];
void init()
{
    t[0]=0;
    for(int i=1;i<=2*n-1;i++)t[i]=t[i-1]+num[i];
}
void cal()
{
    memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=2*n-1;i++) f[i][i]=0;
    for(int k=1;k<n;k++)//length
        for(int i=1;i<=n;i++)//start
            for(int j=i;j<i+k;j++)//mid
            {
                f[i][i+k]=min(f[i][i+k],f[i][j]+f[j+1][i+k]+t[i+k]-t[i-1]);
            }
    //for(int i=1;i<=n;i++)for(int j=i+1;j<=i+n-1;j++) printf("i=%d,j=%d,f=%4dtt",i,j,f[i][j]);
}
int main()
{
    //freopen("cin.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);
        for(int i=n+1;i<=2*n;i++) num[i]=num[i-n];
      //  for(int i=1;i<=2*n-1;i++) printf("i=%d,num=%dn",i,num[i]);
        init();
        cal();
        int maxn=0x3f3f3f3f;
      //  for(int i=1;i<=n;i++) printf("i=%d,j=%d,f=%dn",i,i+n-1,f[i][i+n-1]);
        printf("%dn",f[1][n]);
    }
    return 0;
}