题解 - Vijos

6

简单区间DP
25ms


#include <queue>
#include <cmath>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
int a[201];
int f[201][201];
int main()
{
    int n,s=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[n+i]=a[i];
    }
    for(int i=n*2-1;i>=1;i--)
    {
        for(int j=i+1;j<2*n&&j-i<n;j++)
        {
            for(int k=i;k<=j-1;k++)
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
            }
            s=max(s,f[i][j]);
        }
    }
    printf("%d",s);
    return 0;
}

liweiergg @ 9 个月前

f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
这里是为什么呢
liweiergg @ 9 个月前

for(int len=2;len<=n;len++)
{
for(int i=1;i<=2*n-1-len;i++)
{
int j=len+i-1;
for(int k=i;k<=j-1;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
s=max(s,f[i][j]);
}
}
还有，就是这么写不对吗

6

Blackie LV 6 @ 9 年前

要说的都在程序里：
```c++
#include<iostream>
using namespace std;

int n,head[201],tail[201],f[201][201];
//f[i][j]为起始为i终点为j的链融合生成的最大能量
//head和tail要拓展数组不然越界要考虑模
//珠子 1 2 3 4 5(1) 6(2) 7(3)
//head 1 3 5 7 1 3 5
//tail 3 5 7 1 3 5 7
//没有再考虑4是因为不需要，枚举不到

void read()
{
int i,j,k,len,max1;

cin>>n;
cin>>head[1];
for(i=2; i<=n; i++)
{
cin>>head[i];

tail[i-1]=head[i];
}
tail[n]=head[1];//读入

for(i=n+1; i<=2*n-1; i++)
{
head[i]=head[i-n];
tail[i]=tail[i-n];
}//拓展数组

for(len=1; len<=n; len++)//枚举链长
for(i=1; i<=2*n-1-len; i++)//枚举起始位置
{
j=i+len;//结束位置

for(k=i; k<j; k++)//寻找在中间某一位置断开，把两边合并
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
//从i到j的最大能量=max(当前能量，从i到k的最大能量+从k+1到j的最大能量
//+两颗珠子合并释放的能量)
//注意我们把i到k，k+1到j看做两颗已经合并的珠子，只需把这两颗合并
}

max1=0;
for(i=1; i<=n; i++)
if(f[i][n+i-1]>max1)
max1=f[i][n+i-1];//枚举起始点找最大

cout<<max1<<endl;

return;
}

int main()
{
read();
return 0;
}
```

wzq1w @ 8 年前

好评
Rafe @ 7 年前

讲的很清楚
yyyz108 @ 7 年前

弱弱的问一句，起始位置为什么要-1
liuzhiyuan1234 @ 6 年前

好评，
Anaklusmos @ 6 年前

超级清楚

2

Sanmee360 LV 8 @ 10 年前

var
i,j,k,sum,n:longint;
a:array[1..101]of longint;
f:array[1..2000,1..2000]of longint;
function max(a,b:longint):longint;
begin
if a>b then
exit(a)
else
exit(b);
end;
begin
read(n);
for i:=1 to n do
f[i,i]:=0;
for i:=1 to n do
begin
read(a[i]);
a[i+n]:=a[i];
end;
for i:=2*n-3 downto 1 do
for j:=i+2 to n+i do
for k:=i+1 to j-1 do
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]+a[i]*a[k]*a[j]);
for i:=1 to n do
sum:=max(f[i,i+n],sum);
writeln(sum);
end.

1

饺子铭 LV 4 @ 6 年前

#include<iostream>
#include<cstdio>
using namespace std;
int head[1005],tail[1005],f[1005][1005];
int main()
{
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);
    int i,j,k,x,maxn,n;
    cin>>n;
    cin>>head[1];
    for(i=2; i<=n; i++)
{
    cin>>head[i];
    tail[i-1]=head[i];
}
    tail[n]=head[1];
    for(i=n+1;i<=2*n-1;i++)
    {
        head[i]=head[i-n];
        tail[i]=tail[i-n];
    }
    for(x=1;x<=n;x++)//合并珠子数量
        for(i=1;i<=2*n;i++)//起始位置
    {
        j=i+x;
        for(k=i;k<j;k++)//最后两颗珠子合并位置
          f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);
    }
    maxn=0;
    for(i=1;i<=n;i++)
      if(f[i][n+i-1]>maxn)
        maxn=f[i][n+i-1];
    cout<<maxn<<endl;
    fclose(stdin);fclose(stdout);
}
//f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[i]*a[k+1]);
//从i到j的最大能量=max(当前能量，从i到k的最大能量+从k+1到j的最大能量+两颗珠子合并释放的能量)

1

Admity LV 8 @ 7 年前

一道区间型（环形）DP
其实相当于把整个项链double，在项链后面再接一根一模一样的

与 石子合并 和矩阵连乘都很相似。
首先项链是环状的，我们肯定要把它从某处断开，从哪断开呢？枚举断点即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[201],dp[201][201],maxn,n;

inline int read()//没有用的读入优化
{
    int f=1,res=0;char ch = getchar();
    while(ch>'9'||ch<'0'){if(ch =='-')  f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
    return f*res;
 } 

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=a[n+i]=read();//展开环
    for(int i=(n<<1)-1;i>=1;i--)
    {
        for(int j=i+1;j<(n<<1) && j-i < n;j++)
        {
            for(int k=i;k<=j-1;k++)//枚举断点
            {
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
            }
            maxn=max(maxn,dp[i][j]);
        }
    }
    printf("%d",maxn);
    return 0;
}

1

ATHENS_ LV 9 @ 7 年前

简单处理成环，之后简单DP.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define LL long long 
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=105;
int n;
LL dp[maxn<<1][maxn<<1],ans;
struct node{
    int l,r;
}d[maxn<<1];


int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(d[i].l);d[i+n].l=d[i].l;
        d[i-1].r=d[i+n-1].r=d[i].l;
    }
    for(int len=1;len<=n;len++){
        for(int l=1,r;(r=l+len-1)<2*n;l++){
            for(int k=l;k<r;k++){
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+d[l].l*d[r].r*d[k].r);
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][i+n-1]);
    }
    printf("%lld",ans);
    
    return 0;
}

忘芥 @ 7 年前

SBDP

1

苍山负雪 LV 7 @ 8 年前

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

int n,f[209][209],s[209],ans,i,j,k;

int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i+n]=s[i];
    }
    for(i=n*2-1;i>=1;i--)
        for(j=i+1;j<n*2&&j-i<n;j++)
        {
            for(k=i;k<j;k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[i]*s[k+1]*s[j+1]);
            ans=max(ans,f[i][j]);
        }
    printf("%d\n",ans);
    return 0;
}

0

## (QWER1234ASDF123321) LV 8 @ 4 年前

#include<cstdio>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
const int mx=110;
int n,ans=0;
int a[mx*2],f[mx*2][mx*2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
    for(int i=2;i<=n+1;i++){
        for(int l=1;l+i-1<=n*2;l++){
            int r=l+i-1;
            for(int k=l+1;k<=l+i-2;k++){
                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
            }
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i][n+i]);
    printf("%d",ans);
    return 0;
}

0

SHZhang LV 8 @ 6 年前

#include <cstdio>
#include <algorithm>

using namespace std;

int head[105];
int tail[105];

int f[105][105];

int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", head + i);
    }
    for (int i = 0; i < n - 1; i++) {
        tail[i] = head[i + 1];
    }
    tail[n - 1] = head[0];
    for (int s = 1; s < n; s++) {
        for (int i = 0; i < n; i++) {
            int j = (i + s) % n;
            if (i < j) {
                for (int k = i; k < j; k++) {
                    f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + head[i] * tail[k] * tail[j]);
                }
            } else {
                for (int k = i; k < j || k >= i; k++, k %= n) {
                    f[i][j] = max(f[i][j], f[i][k] + f[(k + 1)%n][j] + head[i] * tail[k] * tail[j]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans = max(ans, f[i][i-1]);
    }
    ans = max(ans, f[0][n-1]);
    printf("%d", ans);
    return 0;
}

0

FxGoethe LV 6 @ 7 年前

环形区间动规，类比矩阵连乘，动规方程式：
F(i,j)=M(i)*M(j)*M(k)+F(i,k)+F(k+1,j)
CK()是用来处理越界数据的，省一点空间，虽然才10^4。

#include<bits/stdc++.h>
using namespace std;
int n,M[101];
long long int F[100][100];//以J为起点，K为终点的区间最优解 

int CK(int a)
{
    if(a>=n)
        return a-n;
    else
        return a;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> M[i];
        F[i][i]=0;
    }
    M[n]=M[0];long long int Mans=0;
    for(int i=1;i<n;i++)
    {//i表示规模,如i=1时表示有两个珠子，即i+1个珠子在区间内 
        for(int j=0;j<n;j++)
        {//j表示起点,终点为 CK(j+i)
            long long int ans=0;
            for(int k=0;k<i;k++)
            {//中间标记为M[j+k+1],前区间[j,j+k],后区间[j+k+1,j+i]
                ans=max(ans,M[j]*M[CK(j+i+1)]*M[CK(j+k+1)]+F[j][CK(j+k)]+F[CK(j+k+1)][CK(j+i)]);
            }
            F[j][CK(j+i)]=ans;
            if(i==n-1)
                Mans=max(Mans,ans);
        }
    }
    cout << Mans;
    return 0;
}

0

ToSoul LV 5 @ 7 年前

一个很简单的区间DP，主要是环变线，想说两点：
1. 用专门的结构体存比较好理解。
2. 答案区间是要尽可能枚举到最右边的，虽然最终答案的区间左端点必定是在【1，N】，但在逐级转移中也可能会出现【N+i，N+j】的一个最优贡献，要考虑到位。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct BALL {
    int l, r;   
};
int N;
BALL B[205];
int A[105], F[205][205];
int main () {
    
    scanf("%d", &N);
    for(int i=1; i<=N; i++) {
        scanf("%d", &A[i]);
        B[i].l=A[i], B[i-1].r=A[i];
    }
    B[N].r=A[1];
    for(int i=1; i<=N; i++) B[i+N]=B[i];
    for(int i=2; i<=N; i++)
        for(int l=1; l+i-1<=2*N; l++) {
            int r=l+i-1;
            for(int k=l; k<r; k++) 
                F[l][r]=max(F[l][r], F[l][k]+F[k+1][r]+B[l].l*B[k].r*B[r].r);
        }  
    int ans=0;   
    for (int i=1; i<=N; i++)
        ans=max(ans, F[i][N+i-1]);
    printf("%d\n", ans);        
    return 0;  
      
}

0

larryzhong LV 9 @ 7 年前

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

int main() {
    int n;
    cin >> n;
    int a[2 * n - 1];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i < n)
            a[i + n] = a[i];
    }
    int f[2 * n - 1][2 * n - 1];
    memset(f, 0, sizeof(f));
    for (int len = 2; len <= n; len++)
        for (int l = 0; l + len - 1 < 2 * n - 1; l++) {
            int r = l + len - 1;
            f[l][r] = 0;
            for (int k = l; k < r; k++)
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
        }
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, f[i][i + n - 1]);
    cout << ans << endl;
    return 0;
}

0

Sky1231 (sky1231) LV 10 @ 8 年前

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

int n,f[200][200],ans=0;

struct node1
{
    int x,y;
}a[200];

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].x);
    a[n].y=a[1].x;
    for (int i=1;i<n;i++)
    {
        a[i].y=a[i+1].x;
        a[i+n]=a[i];
    }
    memset(f,0,sizeof(f));
    for (int l=1;l<=n;l++)
        for (int i=1;i<2*n-l;i++)
            for (int j=i;j<i+l;j++)
                f[i][i+l]=max(f[i][i+l],f[i][j]+f[j+1][i+l]+(a[i].x*a[j].y*a[i+l].y));
    for (int i=1;i<=n;i++)
        ans=max(ans,f[i][i+n-1]);
    printf("%d\n",ans);
}

sky1231 @ 8 年前

大H2O题

0

chronix LV 8 @ 8 年前

#include <cstdio>
#include <algorithm>
#define M 110
using std::max;

int m=0,n,v[M],f[M][M]={0};

int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
for(int j=2;j<=n;j++)
for(int i=0;i<n;i++)
for(int k=1;k<j;k++)
f[i][j]=max(f[i][j],f[i][k]+f[(i+k)%n][j-k]+v[(i+k)%n]*v[i]*v[(i+j)%n]);
for(int i=0;i<n;i++)
m=max(m,f[i][n]);
printf("%d",m);
return 0;
}

0

black_sky_zhang LV 9 @ 8 年前

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 680 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 680 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 680 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 676 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 680 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 680 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 680 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 680 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 680 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 680 KiB, score = 10
Accepted, time = 60 ms, mem = 680 KiB, score = 100
返回代码界面 | 关闭

#include<cstdio>
#include<algorithm>
using namespace std;
int n,f[209][209],a[209],ans=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) {scanf("%d",&a[i]);a[i+n]=a[i];}
for(int i=n*2-1;i>=1;--i)
{
for(int j=i+1;j<n*2&&j-i<n;++j)
{
for(int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
ans=max(ans,f[i][j]);
}
}
printf("%d",ans);
return 0;
}

0

SVIP LV 8 @ 8 年前

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstdlib>
#include<string>
#include<bitset>
#include<iomanip>
#define ll long long
using namespace std;
int n,sum,ans = 0;
int a[205],f[205][205];
int juhe(int i,int k,int j){
sum = a[i] * a[k + 1] * a[j + 1];
return sum;
}
int main(){
//freopen("p1312.in","r",stdin);
//freopen("p1312.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
a[i + n] = a[i];
}
for(int i = 1;i <= 2*n;i++)
f[i][i] = 0;
for(int j = 1;j < 2*n;j++)
for(int i = j;i >= max(1,j - n + 1);i--){
for(int k = i;k < j;k++){
f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]+juhe(i,k,j));
}
}

for(int i = 1;i<=n;i++)
ans=max(ans,f[i][i+n-1]);
printf("%d\n",ans);
return 0;
}

0

tootal (hzq) LV 9 @ 8 年前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 105;
const int M = N << 1;
int n,res = 0,head[M],f[M][M] = {0};
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&head[i]);
head[n + i] = head[i];
}
for(int p = 1;p < n;p++)
for(int i = 1;i < ((n << 1) - 1);i++)
for(int j = min(i + p,(n << 1) - 1),k = i;k < j;k++)
f[i][j] = max(f[i][j],f[i][k] + f[k + 1][j] + head[i] * head[k + 1] * head[j + 1]);
for(int i = 1;i <=n;i++)
res = max(res,f[i][n + i - 1]);
printf("%d\n",res);
return 0;
}

0

LXL LV 8 @ 9 年前

多开1倍的数组，26行搞定
#include <iostream>
using namespace std;
int n,a[205],b[205],f[205][205],x;
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i++ )
{
cin>>a[i];
a[i+n]=a[i];
}
b[n]=a[1];
for(int i = 1 ; i < n ; i++ )
b[i]=b[i+n]=a[i+1];
for(int c=1;c<n;c++)
for(int i=1;i<=2*n-c;i++)
{
x=i+c;
for(int j=i;j<x;j++)
f[i][x]=max(f[i][x],f[i][j]+f[j+1][x]+a[i]*b[j]*b[x]);
}
for(int i=1;i<=n;i++)
f[0][0]=max(f[i][i+n-1],f[0][0]);
cout<<f[0][0];
return 0;
}

0

linhui LV 9 @ 9 年前

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200 + 10;

int a[MAXN], f[MAXN][MAXN];

int main()
{
int n, ans = 0;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
a[i+n] = a[i];
}
for(int j=1; j<2*n; j++){
for(int i=j; i>=max(1, j-n+1); i--){
if(i == j) f[i][j] = 0;
for(int k=i; k<j; k++)
f[i][j] = max(f[i][j], f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
}
if(j >= n)
ans = max(ans, f[j-n+1][j]);
}
printf("%d", ans);
return 0;
}

0

蒋天奇 LV 8 @ 9 年前

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int a[1000],f[1000][1000];
int n;
int main()
{
memset(f,0,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
int maxn=0;
for(int i=2;i<=n+n;i++){
for(int j=i-1;i-j<n&&j>=1;j--){
for(int k=j;k<i;k++){
f[j][i]=max(f[j][i],f[j][k]+f[k+1][i]+a[j]*a[k+1]*a[i+1]);
}
maxn=max(maxn,f[j][i]);
}
}
//for(int i=1;i<=n;i++)maxn=max(maxn,f[i][n+i-1]);
cout<<maxn;
}
只要将一条项链【1，n】连成【1，2n】的一条链即可

题解

160 条题解

能量项链

信息

状态

开发

支持

题解

160 条题解

能量项链

信息

状态

开发

支持

还没有账户？

登录