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

范德萨发发

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. 
   
5. int e,n,maxx=0,a[101][6]={};
   
6. 
   
7. void s(int i)
   
8. {
   
9.         int mm=0;
   
10.         int x=i+1;
    
11.         if(x>n)
    
12.         x=1;
    
13.         for(int j=1;j<n;j++)
    
14.         {
    
15.                 mm=mm+a[i][1]*a[x][1]*a[x][2];
    
16.                 cout<<"首"<<a[i][1]<<" 中"<<a[x][1]<<" 尾"<<a[x][2]<<" x"<<x<<endl;
    
17.                 x=a[x][3];
    
18.         }
    
19.         cout<<mm<<"  "<<endl;
    
20.         cout<<endl;
    
21.         if(maxx<mm)
    
22.                 maxx=mm;
    
23. }
    
24. 
    
25. void ss(int i)
    
26. {
    
27.                 int mm=0;
    
28.         int x=i;
    
29.        
    
30.         for(int j=1;j<n;j++)
    
31.         {
    
32.                 if(x==0)
    
33.                 x=n;
    
34.                 mm=mm+a[i][1]*a[a[x][4]][1]*a[a[a[x][4]][4]][1];
    
35.                 cout<<"首"<<a[i][1]<<" 中"<<a[a[x][4]][1]<<" 尾"<<a[a[a[x][4]][4]][1]<<" x"<<x<<endl;
    
36.                 x=a[x][4];
    
37.         }
    
38.         cout<<mm<<"  "<<endl;
    
39.         cout<<endl;
    
40.         if(maxx<mm)
    
41.                 maxx=mm;
    
42. }
    
43. 
    
44. int main()
    
45. {
    
46.         freopen("in.txt","r",stdin);
    
47.         cin>>n;
    
48.         for(int i=1;i<=n;i++)
    
49.         {
    
50.                 cin>>a[i][1];
    
51.         }
    
52.         a[n+1][1]=a[1][1];
    
53.         for(int i=1;i<=n;i++)
    
54.         {
    
55.                 a[i][2]=a[i+1][1];
    
56.                 a[i][3]=i+1;
    
57.                 a[i][4]=i-1;
    
58.                 a[i][5]=i;
    
59.         }
    
60.         a[n][3]=1;
    
61.         a[n+1][2]=a[1][2];
    
62.         a[1][4]=n;
    
63.         for(int i=1;i<=n;i++)
    
64.         {
    
65.                 s(i);
    
66.                 ss(i);
    
67.         }
    
68.         cout<<maxx;
    
69. }

复制代码

来源————一本通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 是最大的数！
要保证能量最大，就要保证最大的数要从头乘到尾
那怎么总是保留最大的数呢？
最大的数要总是处于头的位置！

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

所以，答案

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int PowerCount(int* beads, int count)
   
6. {
   
7.     int pos      = 0;       //最大的数在数组中的位置开始往后
   
8.     int maxNum   = beads[0];//最大的数
   
9.     int next     = 0;       //pos的下个位置
   
10.     int result   = 0;       //结果
    
11.     int i        = 0;       //临时变量
    
12. 
    
13.     //首先找到最大的数在数组中的位置 -- 从第2个数开始
    
14.     for (i = 1; i < count; ++i)
    
15.     {
    
16.         if(beads[i] > beads[i - 1])
    
17.         {
    
18.             pos = i;
    
19.             maxNum = beads[i];
    
20.         }
    
21.     }
    
22. 
    
23.     //然后按公式求和 -- 从最大的数开始往后
    
24.    
    
25.     i = 1;      //计算次数为 数组个数 - 1
    
26. 
    
27.     do
    
28.     {
    
29.         pos += 1;
    
30.         if(pos >= count)
    
31.             pos = 0;
    
32. 
    
33.         next = pos + 1;
    
34.         if(next >= count)
    
35.             next = 0;
    
36. 
    
37.         result += maxNum * beads[pos] * beads[next];
    
38. 
    
39.         ++i;
    
40.     } while (i < count);    //这里 i 只用于记录次数
    
41. 
    
42.     return result;
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     int beads[] = { 2, 3, 5, 10 };
    
48. 
    
49.     cout << PowerCount(beads, 4) << endl;
    
50. 
    
51.     return 0;
    
52. }

复制代码

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

跳转到最佳答案楼层

Gacy

C++我的痛苦

yuxijian2020

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

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

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

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

所以，答案

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int PowerCount(int* beads, int count)
   
6. {
   
7.     int pos      = 0;       //最大的数在数组中的位置开始往后
   
8.     int maxNum   = beads[0];//最大的数
   
9.     int next     = 0;       //pos的下个位置
   
10.     int result   = 0;       //结果
    
11.     int i        = 0;       //临时变量
    
12. 
    
13.     //首先找到最大的数在数组中的位置 -- 从第2个数开始
    
14.     for (i = 1; i < count; ++i)
    
15.     {
    
16.         if(beads[i] > beads[i - 1])
    
17.         {
    
18.             pos = i;
    
19.             maxNum = beads[i];
    
20.         }
    
21.     }
    
22. 
    
23.     //然后按公式求和 -- 从最大的数开始往后
    
24.    
    
25.     i = 1;      //计算次数为 数组个数 - 1
    
26. 
    
27.     do
    
28.     {
    
29.         pos += 1;
    
30.         if(pos >= count)
    
31.             pos = 0;
    
32. 
    
33.         next = pos + 1;
    
34.         if(next >= count)
    
35.             next = 0;
    
36. 
    
37.         result += maxNum * beads[pos] * beads[next];
    
38. 
    
39.         ++i;
    
40.     } while (i < count);    //这里 i 只用于记录次数
    
41. 
    
42.     return result;
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     int beads[] = { 2, 3, 5, 10 };
    
48. 
    
49.     cout << PowerCount(beads, 4) << endl;
    
50. 
    
51.     return 0;
    
52. }

复制代码

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


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

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

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

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

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

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

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

1. 
   
2. [code]#include<cstdio>
   
3. #include<iostream>
   
4. #include<algorithm>
   
5. #include<cstring>
   
6. #include<cmath>
   
7. #define nn 2*n-1
   
8. using namespace std;
   
9. int dp[500][500],head[500],tail[500],n,ans;
   
10. int main()
    
11. {
    
12.         cin>>n;
    
13.         for(int i=1;i<=n;i++){
    
14.                 scanf("%d",&head[i]);
    
15.                 head[n+i]=head[i];
    
16.         }
    
17.         for(int i=1;i<=nn;i++) tail[i]=head[i%n+1];
    
18.         for(int i=1;i<=nn;i++) dp[i][i]=0;
    
19.         for(int t=1;t<n;t++){
    
20.                 for(int i=1;i<=nn;i++){
    
21.                         int j=i+t;
    
22.                         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]);
    
23.                 }
    
24.         }
    
25.         for(int i=1;i<=nn;i++) ans=max(ans,dp[i][i+n-1]);
    
26.         cout<<ans;
    
27.        
    
28.         return 0;
    
29. }

复制代码

[/code]

范德萨发发

1. for(int i=n-1;i>=1;i--)
   
2.         {
   
3.                 for(int j=i+1;j<=n;j++)
   
4.                 {
   
5.                         for(int k=i;k<=j-1;k++)
   
6.                         {
   
7.                                 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
   
8. //                                cout<<f[i][j]<<"  ";
   
9.                         }
   
10.                 }
    
11.         }

复制代码

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