论坛 › C\C++交流 › 我写的这个程序怎么过不了啊？

范德萨发发 发表于 2021-6-14 12:41:08

我写的这个程序怎么过不了啊？

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

int e,n,maxx=0,a={};

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*a*a;
                cout<<"首"<<a<<" 中"<<a<<" 尾"<<a<<" x"<<x<<endl;
                x=a;
        }
        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*a]*a]];
                cout<<"首"<<a<<" 中"<<a]<<" 尾"<<a]]<<" x"<<x<<endl;
                x=a;
        }
        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;
        }
        a=a;
        for(int i=1;i<=n;i++)
        {
                a=a;
                a=i+1;
                a=i-1;
                a=i;
        }
        a=1;
        a=a;
        a=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
23510
【输出样例】
710

Gacy 发表于 2021-6-14 21:52:56

C++我的痛苦

yuxijian2020 发表于 2021-6-14 22:34:47

本帖最后由 yuxijian2020 于 2021-6-15 17:21 编辑

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

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

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

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

所以，答案
#include <iostream>

using namespace std;

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

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

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

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

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

      result += maxNum * beads * beads;

      ++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) -- 常数个数的变量

范德萨发发 发表于 2021-6-20 09:26:23

最佳答案过不了
记忆化递归搜索方式解决：根据题意，首先要清楚，本题无法通过贪心的方式解答。
最后一次合并，两颗珠子合并成一颗珠子，共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*tail*tail, f(1,2)+f(3,n)+ head*tail*tail，。。。。。，f(1,n-1)+f(n,n)+ head*tail*tail)

对于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*tail*tail)
}
边界条件 f(k,k)＝0
通过简单递归搜索，很可能超时，仔细观察发现，里面有很多小段的珠子能量
会重复计算合并，本题需采用记忆化递归搜索。


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

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

dp=max(dp+dp+head*tail*tail)，其中head为头标记，tail为尾标记。

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

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

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

时间复杂度O（n^3）。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define nn 2*n-1
using namespace std;
int dp,head,tail,n,ans;
int main()
{
        cin>>n;
        for(int i=1;i<=n;i++){
                scanf("%d",&head);
                head=head;
        }
        for(int i=1;i<=nn;i++) tail=head;
        for(int i=1;i<=nn;i++) dp=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=max(dp,dp+dp+head*tail*tail);
                }
        }
        for(int i=1;i<=nn;i++) ans=max(ans,dp);
        cout<<ans;
       
        return 0;
}

范德萨发发 发表于 2021-6-20 13:03:53

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=min(f,f+f+s-s);
//                                cout<<f<<"";
                        }
                }
        }
解释一下，i就不说了，j是从i开始的可以到达的一个末尾，k是在ij直接切开一段进行计算，s数组是前n项的和

查看完整版本: 我写的这个程序怎么过不了啊？