C/C++教程

动态规划:P5569 [SDOI2008] 石子合并 GarsiaWachs算法

本文主要是介绍动态规划:P5569 [SDOI2008] 石子合并 GarsiaWachs算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
P5569 [SDOI2008] 石子合并

 

 

 

 

    这题就是P1775石子合并的数据加强版,我们那题采用的是区间DP,时间复杂度为O(n3) (4*1e4)的三次方=1.6*1e13,显然超时。这里就必须用一个算法,叫做GarsiaWachs算法,可以降低时间复杂度至n2甚至nlogn.

    GarsiaWachs算法:他的做法就是对于一个序列a,先int ans=0,然后从左到右找到a[k-1]<a[k+1],将a[k]和a[k-1]合并成一个新的元素a[temp],从a[k-1]向左寻找,找到第一个比他大的,插入在他后面,ans+=a[temp],注意要把a[-1]和a[终点]定义为无穷大,方便寻找插入。然后再重复这个操作,直到序列中没有a[k-1]<a[k+1].原理我也不会推导,只知道这么个结论。

    这是我的代码:利用stl来操作,但是要开O2优化,否则只有70分,T3个点。

 1 //GarsiaWachs
 2 //开O2
 3 #include<iostream>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<climits>//INT_MAX的头文件
 8 using namespace std;
 9 int read()
10 {
11     int f = 1;
12     int ans = 0;
13     char c = getchar();
14     if (c > '9' || c < '0')
15     {
16         f = -1;
17         c = getchar();
18     }
19     while (c >= '0' && c <= '9')
20     {
21         ans = (ans << 1) + (ans << 3) + (c - '0');
22         c = getchar();
23     }
24     return f * ans;
25 }
26 int main()
27 {
28     int n;
29     n = read();
30     vector<int>v;
31     v.push_back(INT_MAX - 1);
32     for (int i = 1; i <= n; ++i)
33     {
34         v.push_back(read());
35     }
36     v.push_back(INT_MAX);
37     int k, j, temp, sum = 0;
38     while (n-- > 1)
39     {
40         for (k = 1; k <= n; ++k)
41         {
42             if (v[k - 1] < v[k + 1])
43                 break;
44         }
45         temp = v[k - 1] + v[k];
46         for (j = k - 1; j >= 0; --j)
47         {
48             if (v[j] > temp)
49                 break;
50         }
51         v.erase(v.begin() + k - 1);//删掉k-1;
52         v.erase(v.begin() + k - 1);//删掉k
53         v.insert(v.begin() + j + 1, temp);//插入和
54         sum += temp;
55     }
56     cout << sum;
57     return 0;
58 
59 }

 

没开O2:

 

 开O2:

 

 

最后补充一下:这个GarsiaWachs算法的标准代码模板,时间复杂度也特别低,高效通过,但是我看了很久也理解不了他的原理。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=50005;
 4 
 5 int n;
 6 int a[maxn];
 7 int num;
 8 int ans;
 9 
10 void combine(int k){
11 
12     int temp=a[k]+a[k-1];
13     ans+=temp;
14     for (int i=k;i<num-1;i++){
15         a[i]=a[i+1];
16     }
17     num--;
18 
19     int j=0;
20     for (j=k-1;j>0&&a[j-1]<temp;j--){
21         a[j]=a[j-1];
22     }
23     a[j]=temp;
24 
25     while (j>=2&&a[j]>=a[j-2]){
26         int d=num-j;
27         combine(j-1);
28         j=num-d;
29     }
30 }
31 
32 int main()
33 {
34     cin >> n;
35     for (int i=0;i<n;i++){
36         cin >> a[i];
37     }
38     num=1;
39     ans=0;
40     for (int i=1;i<n;i++){
41         a[num++]=a[i];
42         while (num>=3&&a[num-3]<=a[num-1]){
43             combine(num-2);
44         }
45     }
46     while (num>1){
47         combine(num-1);
48     }
49 
50     cout << ans << endl;
51 }

 

 

 

 

    

这篇关于动态规划:P5569 [SDOI2008] 石子合并 GarsiaWachs算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!