From Sleeping

能量项链 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

郁闷,去年只过了7个点.

石子归并，简单动规

反思..考试的时候我在干嘛........

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

违反能量守衡定律啊！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 20ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：20ms

程序有点猥琐...要是换Vivid Puppy肯定0ms了...

晕

当时看题时以为是按顺序合并

后来才知道是石子合并

告别赛啊，郁闷

当N=100时

谁能发下O（N^3)或O（N^2LOGN)的思路

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

正宗的石子归并……

考试的时候我没有看出来，用贪心做，才得了10分~~~

无语……ˇ_ˇ

不哼不哈，太......

石子归并，串两次成长度为2N的纪录数组list。

每次决策取max{f[k,j]+f+list[j].x*list[j+k].x*list.y};

编起来费时，贪心性价比高啊，NOIP时10分钟拿了30分……

在提高组排第一题....我晕..李学武把一道DP题排第一题...害死我了...55555555~

第一次用DP忘了断开处的细节，做好才10分，还好比赛时用的贪心，要不连30都没了……

我也是O(N^4),不过是100分^_^

我NOIP这题得10分，这次把程序重打一遍就过了，原来没开Longint(开成integer)!

郁闷！

把一条链打开，串成2n长度的链，用石子归并

NOIP郁闷ing～

啊，是这样啊..................

环形。。石子归并.....为什么我在考试的时候没写出来？？？

总算会做了......环形的,环形的,环形的......

DP O（n^3）

#include<cstdio>
#include<algorithm>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}
int ans,n,a[202],dp[202][202];
int main()
{
    read(n);
    for (register int i=1;i<=n;++i) read(a[i]),a[i+n]=a[i];
    for (register int i=2;i<=(n<<1);++i)
     for (register int v=i-1;v&&i-v<n;--v)
      for (register int j=v;j<i;++j)
       dp[v][i]=max(dp[v][i],dp[v][j]+dp[j+1][i]+a[v]*a[j+1]*a[i+1]),ans=max(ans,dp[v][i]);
    printf("%d",ans);
    return 0;
}