[已解决]我写的这个程序怎么过不了啊？

范德萨发发

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

int e,n,maxx=0,a[101][6]={};

void s(int i)
{
        int mm=0;
        int x=i+1;
        if(x>n)
        x=1;
        for(int j=1;j<n;j++)
        {
                mm=mm+a[i][1]*a[x][1]*a[x][2];
                cout<<"首"<<a[i][1]<<" 中"<<a[x][1]<<" 尾"<<a[x][2]<<" x"<<x<<endl;
                x=a[x][3];
        }
        cout<<mm<<"  "<<endl;
        cout<<endl;
        if(maxx<mm)
                maxx=mm;
}

void ss(int i)
{
                int mm=0;
        int x=i;
        
        for(int j=1;j<n;j++)
        {
                if(x==0)
                x=n;
                mm=mm+a[i][1]*a[a[x][4]][1]*a[a[a[x][4]][4]][1];
                cout<<"首"<<a[i][1]<<" 中"<<a[a[x][4]][1]<<" 尾"<<a[a[a[x][4]][4]][1]<<" x"<<x<<endl;
                x=a[x][4];
        }
        cout<<mm<<"  "<<endl;
        cout<<endl;
        if(maxx<mm)
                maxx=mm;
}

int main()
{
        freopen("in.txt","r",stdin);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i][1];
        }
        a[n+1][1]=a[1][1];
        for(int i=1;i<=n;i++)
        {
                a[i][2]=a[i+1][1];
                a[i][3]=i+1;
                a[i][4]=i-1;
                a[i][5]=i;
        }
        a[n][3]=1;
        a[n+1][2]=a[1][2];
        a[1][4]=n;
        for(int i=1;i<=n;i++)
        {
                s(i);
                ss(i);
        } 
        cout<<maxx;
}

来源————一本通c++
1843：【06NOIP提高组】能量项链

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 535     通过数: 322
【题目描述】
在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），当i＜N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

【输出】
只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。

【输入样例】
4
2  3  5  10
【输出样例】
710

最佳答案

月排行榜 / 总排行榜

yuxijian2020

2021-6-14 22:34:47

这种题目，一般都有时间，空间要求
而且不是很难的话  对时间、空间要求就更严
所以不要抬手就写，分析一下

首先，聚合能量的公式 是  前首 * 前尾 * 后尾(或者说 前首 * 后首 * 后尾 )
那么，题目中要求的 总能量最大 是要满足什么条件呢？

看看例子， 2 3 5 10
是从最后一个珠子开始聚合，为什么？
因为 10 是最大的数！
要保证能量最大，就要保证最大的数要从头乘到尾
那怎么总是保留最大的数呢？
最大的数要总是处于头的位置！

所以，此时再看题目就很简单的
说白了就是找到最大的数  然后按照公式计算结果输出就可以了

所以，答案

#include <iostream>

using namespace std;

int PowerCount(int* beads, int count)
{
    int pos      = 0;       //最大的数在数组中的位置开始往后
    int maxNum   = beads[0];//最大的数
    int next     = 0;       //pos的下个位置
    int result   = 0;       //结果
    int i        = 0;       //临时变量

    //首先找到最大的数在数组中的位置 -- 从第2个数开始
    for (i = 1; i < count; ++i)
    {
        if(beads[i] > beads[i - 1])
        {
            pos = i;
            maxNum = beads[i];
        }
    }

    //然后按公式求和 -- 从最大的数开始往后
    
    i = 1;      //计算次数为 数组个数 - 1

    do
    {
        pos += 1;
        if(pos >= count)
            pos = 0;

        next = pos + 1;
        if(next >= count)
            next = 0;

        result += maxNum * beads[pos] * beads[next];

        ++i;
    } while (i < count);    //这里 i 只用于记录次数

    return result;
}

int main()
{
    int beads[] = { 2, 3, 5, 10 };

    cout << PowerCount(beads, 4) << endl;

    return 0;
}

时间复杂度 O(n) -- 遍历2次数组
空间复杂度 O(1) -- 常数个数的变量

跳转到最佳答案楼层

Gacy

C++我的痛苦

yuxijian2020

这种题目，一般都有时间，空间要求
而且不是很难的话  对时间、空间要求就更严
所以不要抬手就写，分析一下

首先，聚合能量的公式 是  前首 * 前尾 * 后尾(或者说 前首 * 后首 * 后尾 )
那么，题目中要求的 总能量最大 是要满足什么条件呢？

看看例子， 2 3 5 10
是从最后一个珠子开始聚合，为什么？
因为 10 是最大的数！
要保证能量最大，就要保证最大的数要从头乘到尾
那怎么总是保留最大的数呢？
最大的数要总是处于头的位置！

所以，此时再看题目就很简单的
说白了就是找到最大的数  然后按照公式计算结果输出就可以了

所以，答案

#include <iostream>

using namespace std;

int PowerCount(int* beads, int count)
{
    int pos      = 0;       //最大的数在数组中的位置开始往后
    int maxNum   = beads[0];//最大的数
    int next     = 0;       //pos的下个位置
    int result   = 0;       //结果
    int i        = 0;       //临时变量

    //首先找到最大的数在数组中的位置 -- 从第2个数开始
    for (i = 1; i < count; ++i)
    {
        if(beads[i] > beads[i - 1])
        {
            pos = i;
            maxNum = beads[i];
        }
    }

    //然后按公式求和 -- 从最大的数开始往后
    
    i = 1;      //计算次数为 数组个数 - 1

    do
    {
        pos += 1;
        if(pos >= count)
            pos = 0;

        next = pos + 1;
        if(next >= count)
            next = 0;

        result += maxNum * beads[pos] * beads[next];

        ++i;
    } while (i < count);    //这里 i 只用于记录次数

    return result;
}

int main()
{
    int beads[] = { 2, 3, 5, 10 };

    cout << PowerCount(beads, 4) << endl;

    return 0;
}

时间复杂度 O(n) -- 遍历2次数组
空间复杂度 O(1) -- 常数个数的变量

范德萨发发

最佳答案过不了
记忆化递归搜索方式解决：根据题意，首先要清楚，本题无法通过贪心的方式解答。
最后一次合并，两颗珠子合并成一颗珠子，共n种情况，珠子呈环状结构。即第1种情况，从1号珠子开始，连续的n个珠子合并，第2种情况，从2号珠子开始，连续的n个珠子合并，。。。。。，第n种情况，从n号珠子开始，连续n个珠子合并。最终需要从这n种情况中选择最大总能量。因为能量珠连成环，处理不方便，所以把它展开成链。把原先的n个能量珠扩成2n-1个，第i个和第i+n个相同。总能量ans可以表示成
ans=max（f(1,n),f(2,n+1),f(3,n+2),…….f(n,2n-1)）,其中f(1,n)表示从1号珠子开始到n号珠子结束，能获得的最大能量。
对于f(1,n)，是最终由两颗珠子合并而成，若干种情况，如，1,2--n；1--2,3--n；。。。。。。1--n-1，n，从这若干种情况中选择能量最大的
求解过程可以表示成
Ans=max(f(1,1)+f(2,n)+ head[1]*tail[1]*tail[n], f(1,2)+f(3,n)+ head[1]*tail[2]*tail[n]，。。。。。，f(1,n-1)+f(n,n)+ head[1]*tail[n-1]*tail[n])

对于f(1,1)，f(2,n) 。。。。。。。f(1,n-1)，f(n,n)，同理可求
由此可见，可以通过递归搜索的方式解决问题。
f(i,j)
{
ans=0;
for(int k=i;k<j;k++)
  ans=max(ans,f(i,k)+f(k+1,j)+ head[i]*tail[k]*tail[j])
}
边界条件 f(k,k)＝0
通过简单递归搜索，很可能超时，仔细观察发现，里面有很多小段的珠子能量
会重复计算合并，本题需采用记忆化递归搜索。


动态规划方式解决：
对于区间[i,j]合并成的能量珠，它一定是由两个能量珠合并而来，我们假设它是由[i,k]和[k+1,j]合并成的。

记dp[i][j]为合并成[i,j]获得的最大能量，我们枚举断点k，那么我们很容易得出状态转移方程

dp[i][j]=max(dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j])，其中head为头标记，tail为尾标记。

因为能量珠连成环，处理不方便，所以把它展开成链。

我们把原先的n个能量珠扩成2n-1个，第i个和第i+n个相同，我们只需要进行DP后找出max（dp[i][i+n-1]）就是答案。

枚举合并的次数t，枚举i，那么j就是i+n，枚举k，进行转移即可。

时间复杂度O（n^3）。

[code]#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define nn 2*n-1
using namespace std;
int dp[500][500],head[500],tail[500],n,ans;
int main()
{
        cin>>n;
        for(int i=1;i<=n;i++){
                scanf("%d",&head[i]);
                head[n+i]=head[i];
        }
        for(int i=1;i<=nn;i++) tail[i]=head[i%n+1];
        for(int i=1;i<=nn;i++) dp[i][i]=0;
        for(int t=1;t<n;t++){
                for(int i=1;i<=nn;i++){
                        int j=i+t;
                        for(int k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+head[i]*tail[k]*tail[j]);
                }
        }
        for(int i=1;i<=nn;i++) ans=max(ans,dp[i][i+n-1]);
        cout<<ans;
        
        return 0;
}

[/code]

范德萨发发

for(int i=n-1;i>=1;i--)
        {
                for(int j=i+1;j<=n;j++)
                {
                        for(int k=i;k<=j-1;k++)
                        {
                                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
//                                cout<<f[i][j]<<"  ";
                        }
                }
        }

解释一下，i就不说了，j是从i开始的可以到达的一个末尾，k是在ij直接切开一段进行计算，s数组是前n项的和