bzoj3229

maksyuki 发表于 oj 分类，标签: DP-区间DP

27 8月 2015

3229: [Sdoi2008]石子合并

Description

在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将N堆石子合并成一堆的最小得分。

Input

第一行是一个数N。

以下N行每行一个数A，表示石子数目。

Output

共一个数，即N堆石子合并成一堆的最小得分。

Sample Input

4
1
1
1
1

Sample Output

HINT

对于 100% 的数据，1≤N≤40000

对于 100% 的数据，1≤A≤200

题目类型：石子合并(GarsiaWachs)

算法分析：直接使用GarsiaWachs算法求解即可，最好使用平衡树进行优化，否则有可能会TLE!!!!!!

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 500000 + 66;

int stone[maxn];
int n, t, ans;

void Combine (int k)
{
    int temp = stone[k] + stone[k-1];
    ans += temp;
    for (int i = k; i < t - 1; i++)
        stone[i] = stone[i+1];
    t--;

    int j = 0;
    for(j = k - 1; j > 0 && stone[j-1] < temp; j--)
        stone[j] = stone[j-1];
    stone[j] = temp;

    while (j >= 2 && stone[j] >= stone[j-2])
    {
        int d = t - j;
        Combine (j - 1);
        j = t - d;
    }
}

void Solve ()
{
    t = 1, ans = 0;
    for (int i = 1; i < n; i++)
    {
        stone[t++] = stone[i];
        while (t >= 3 && stone[t-3] <= stone[t-1])
            Combine (t - 2);
    }
    while (t > 1) Combine (t - 1);
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    scanf ("%d", &n);

    for (int i = 0; i < n; i++)
        scanf ("%d", &stone[i]);

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

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 500000 + 66;

int stone[maxn];

int n, t, ans;

void Combine (int k)

{

int temp = stone[k] + stone[k-1];

ans += temp;

for (int i = k; i < t - 1; i++)

stone[i] = stone[i+1];

t--;

int j = 0;

for(j = k - 1; j > 0 && stone[j-1] < temp; j--)

stone[j] = stone[j-1];

stone[j] = temp;

while (j >= 2 && stone[j] >= stone[j-2])

{

int d = t - j;

Combine (j - 1);

j = t - d;

}

void Solve ()

{

t = 1, ans = 0;

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

{

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

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

Combine (t - 2);

}

while (t > 1) Combine (t - 1);

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

scanf ("%d", &n);

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

scanf ("%d", &stone[i]);

Solve ();

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

return 0;

}

bzoj2818

lightoj1002

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

超客的水墨烟雨