DP

Time Limit:3000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu

Submit Status Practice HYSBZ 3229

Description

　　桌上有一排 N 堆饭团。现要将饭团合并成一堆。规则是

每次只能选相邻的 2 堆饭团合并成新的一堆，并将新的一堆饭团数记为这次操作的分数。

　　将 N 堆饭团合并成一堆的最小总分。

Input

　　第一行N(N<=40000) 。

　　以下每行一个数 x(x<=200) ，表示饭团数目。

Output

　　输出最小总分。

Sample Input

Sample Output

8

//只能 Garsiawachs 解，因为数据很大，时间，空间，一般 DP 都不行
代码看了别人的，代码不难，但是原理难啊，看了很久都不懂。。。先放放，学了哈夫曼树再看看
82ms

 //GarsiaWachs算法 0ms

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int N = ;

 int stone[N];

 int n,t,ans;

 void combine(int k);

 int main()

 {

     while(cin>>n)

     {

         for(int i=;i<n;i++)

             scanf("%d",stone+i);

         t = ;

         ans = ;

         for(int i=;i<n;i++)

         {

             stone[t++] = stone[i];

             while(t >=  && stone[t-] <= stone[t-])

                 combine(t-);

         }

         while(t > )//大于1堆，从最右边那堆开始向左合并

             combine(t-);

         printf("%d\n",ans);

     }

     return ;

 }

 void combine(int k)

 {

     int tmp = stone[k] + stone[k-];

     ans += tmp;

     for(int i=k;i<t-;i++)//后面的往前移，移到位置 k

         stone[i] = stone[i+];

     t--;

     int j = ;

     for(j=k-;j> && stone[j-] < tmp;j--)//厉害了，不断往前移坑，

         stone[j] = stone[j-];

     stone[j] = tmp;//填坑

     while(j >=  && stone[j] >= stone[j-])//如果调整后，又比前2个大，即又是那个条件达成了

     {

         int d = t - j;//记录与堆数的差值

         combine(j-);

         j = t - d;//少了几堆就向前移动了几次，位置也变为几

     }

 }

巴特西

石子合并DP

DP

最新文章

热门文章