现在的位置: 首页 > 综合 > 正文

ivision (DP_斜率优化|四边形不等式优化) Hdu 3480 Division (DP_斜率优化|四边形不等式优化)Hdu 2829 Lawrence (DP_四边形优化|斜率优化)

2017年11月04日 ⁄ 综合 ⁄ 共 9906字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

Hdu 3480 Division (DP_斜率优化|四边形不等式优化)

分类： 全部博客 ACM_动态规划(DP)2012-08-25
15:58 507人阅读 评论(3) 收藏 举报

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3480

题目大意：给定一个大小为n的集合，要求将集合分成m个子集合，每个集合都有权值，权值为最大值减最小值的平方。m<=5000，n<=10000.

解题思路：还算简单的优化DP吧，因为一眼就能看出是DP而且需要优化。

     要将集合分成m个子集合，并且权值和最小，容易想到对集合元素进行排序，能排序的前提是排序完再划分集合，那么此时划分的集合权值总和将和没排序时的相比相等或者更小，并且使得计算更加容易。比如a<b<c<d，那么(d-a)^2 + (c-b)^2 > (b-a)^2 + (d-c)^2. 

    对于排序完的集合， 状态转移方程为:dp[i][j+1] = Min {dp[k][j] + (arr[i] - arr[k+1])^2}(k < i),朴素的做法复杂度是O(n*m*n)，太可怕了。然后呢，就想到斜率优化或者四边形不等式优化了。

    这题既能用斜率优化也能用四边形不等式优化，而斜率优化比四边形不等式优化常数更小，速度更快，本文章着重讲斜率优化，据lasten大神说斜率优化能过的题目四边形不等式都能过，不知可信不可信。

    dp[i][j+1] = min{dp[k][j] + (arr[i] - arr[k+1]) ^2} = dp[k][j] + arr[i]^2 + arr[k+1]^2 - 2 * arr[i] * arr[k+1].

    设y = dp[k][j] + arr[k+1]^2,x = arr[k+1],,那么dp[i][j] = y - 2 * arr[i] * x，转化成这样就可以开始套模版了。

    这题我写了很多遍，一拿到题目用四边形就ac了。然后开始用斜率优化写，之前都是写dp[i][j+1] = dp[k][j] + sum[i] + sum[k] - 2 * sum[i][k]，这种和只k有关的DP，用别人的模版倒挺顺的，现在换成了和K+1有关就不知道该怎么搞了。晕了好久，直到今天做网络热身赛遇到差不多的题目才想清楚。其实本质是一样的，写法也是一样，但要先处理j==1的的情况。因为这种时候dp[i][1] = (arr[i] - arr[1])^2都是从0转移过来的，可以不跑单调队列。

测试数据：

Input:
10
3 1
1 2 3
3 2
1 2 2
3 2
1 2 4
4 2
4 7 10 1

OutPut:
Case 1: 4
Case 2: 0
Case 3: 1
Case 4: 18


C艹代码：

[cpp] view
plaincopy

  1. //斜率优化DP  
  2. #include <stdio.h>  
  3. #include <string.h>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. #define MIN 5010  
  7. #define MAX 10010  
  8. #define INF 2147483647;  
  9.   
  10.   
  11. struct point{  
  12.   
  13.     int x,y;  
  14. }pot[MAX];  
  15. int dp[MAX][MIN];  
  16. int qu[MAX],head,tail;  
  17. int n, m, arr[MAX];  
  18.   
  19.   
  20. int CheckIt(int x,int y,int z) {  
  21.   
  22.     point p0 = pot[x],p1 = pot[y],p2 = pot[z];  
  23.     return (p0.x - p1.x) * (p0.y - p2.y) - (p0.y - p1.y) * (p0.x - p2.x) <= 0;  
  24. }  
  25. int NotBest(int x,int y,int k) {  
  26.   
  27.     point p0 = pot[x],p1 = pot[y];  
  28.     return p0.y - p0.x * k > p1.y - p1.x * k;  
  29. }  
  30. int Solve_DP() {  
  31.   
  32.     int i, j, k, mmin;  
  33.   
  34.   
  35.     for (i = 1; i <= n; ++i)  
  36.         dp[i][1] = (arr[i] - arr[1]) * (arr[i] - arr[1]);  
  37.     for (j = 2; j <= m; ++j) {  
  38.   
  39.         head = tail = 0;  
  40.         for (i = j; i <= n; ++i) {  
  41.   
  42.             pot[i].x = arr[i];  
  43.             pot[i].y = dp[i-1][j-1] + arr[i] * arr[i];  
  44.             while (head <= tail - 1 &&  
  45.                     CheckIt(qu[tail-1],qu[tail],i)) tail--;  
  46.             qu[++tail] = i;  
  47.   
  48.   
  49.             while (head + 1 <= tail &&  
  50.                     NotBest(qu[head],qu[head+1],2*arr[i])) head++;  
  51.             k = qu[head];  
  52.             dp[i][j] = pot[k].y - 2 * pot[k].x * arr[i] + arr[i] * arr[i];  
  53.         }  
  54.     }  
  55.     return dp[n][m];  
  56. }  
  57.   
  58.   
  59. int main()  
  60. {  
  61.     int i, j, k, t, cas = 0;  
  62.   
  63.   
  64.     scanf("%d", &t);  
  65.     while (t--) {  
  66.   
  67.         scanf("%d%d", &n, &m);  
  68.         for (i = 1; i <= n; ++i)  
  69.             scanf("%d", &arr[i]);  
  70.           
  71.           
  72.         sort(arr + 1, arr + 1 + n);  
  73.         int ans = Solve_DP();  
  74.         printf("Case %d: %d\n", ++cas, ans);  
  75.     }  
  76. }  
[cpp] view
plaincopy

  1. //四边形不等式优化  
  2. #include <stdio.h>  
  3. #include <string.h>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. #define MAX 5010  
  7. #define INF 2147483647;  
  8.   
  9.   
  10. int dp[MAX * 2][MAX];  
  11. int n, m, arr[MAX * 2], s[MAX * 2][MAX];  
  12.   
  13. int Solve() {  
  14.   
  15.     int i, j, k, mmin;  
  16.   
  17.   
  18.     for (j = 1; j <= m; ++j) s[n + 1][j] = n;  
  19.     for (i = 1; i <= n; ++i)  
  20.         dp[i][1] = (arr[i] - arr[1]) * (arr[i] - arr[1]),s[i][1] = 0;  
  21.     for (j = 2; j <= m; ++j)  
  22.         for (i = n; i >= 1; --i) {  
  23.   
  24.             int mmin = INF;  
  25.             for (k = s[i][j - 1]; k <= s[i + 1][j] && k < i; ++k)  
  26.                 if (dp[k][j - 1] + (arr[i] - arr[k + 1]) * (arr[i] - arr[k + 1]) < mmin)  
  27.                     mmin = dp[k][j - 1] + (arr[i] - arr[k + 1]) * (arr[i] - arr[k + 1]), s[i][j] = k;  
  28.             dp[i][j] = mmin;  
  29.         }  
  30.   
  31.   
  32.    return dp[n][m];  
  33. }  
  34.   
  35.   
  36. int main() {  
  37.     int i, j, k, t, cas = 0;  
  38.   
  39.   
  40.     scanf("%d", &t);  
  41.     while (t--) {  
  42.   
  43.         scanf("%d%d", &n, &m);  
  44.         for (i = 1; i <= n; ++i)  
  45.             scanf("%d", &arr[i]);  
  46.         sort(arr + 1, arr + 1 + n);  
  47.   
  48.   
  49.         int ans = Solve();  
  50.         printf("Case %d: %d\n", ++cas, ans);  
  51.     }  
  52. }  

 

Hdu 2829 Lawrence (DP_四边形优化|斜率优化)

分类： 全部博客 ACM_好题经典题 ACM_动态规划(DP)2012-08-23
16:42 430人阅读 评论(0) 收藏 举报

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2829

题目大意：给定一个长度为n的序列，至多将序列分成m段，每段序列都有权值，权值为序列内两个数两两相乘之和。m<=n<=1000.

解题思路：经典的DP优化题，可以用四边形不等式优化也可以用斜率优化，我三种方法实现，两种斜率优化，一种四边形不等式，其中复杂度都为n*m，但是常熟略有差异。

    状态转移方程很好想，dp[i][j] = min(dp[i][j],dp[k][j-1]+cost[k+1][j])(1<=k<i),这种方程普通写法是n*n*m，当n为1000时运算量为10亿级别，必须优化。

    

     第一种：四边形不等式优化，这种方法是最简单的，主要是减少枚举k的次数。cost[i][j]是某段区间的权值，当区间变大，权值也随之变大，区间变小，权值也随之变小，此时就可以用四边形不等式优化。

     我们设s[i][j]为dp[i][j]的前导状态，即dp[i][j] = dp[s[i][j][j-1] + cost[s[i][j]+1][j].之后我们枚举k的时候只要枚举s[i][j-1]<=k<=s[i+1][j],此时j必须从小到大遍历，i必须从大到小。

     用这种方法我的代码跑了140ms。

    第二种：斜率优化.其实是借鉴大牛大思路，Here，我只是抛砖引玉而已。这种方法的dp和suma数组必须为64位整数，因为平方和会超过32位整数。

    用这种方法我的代码跑了350ms。

    第三种:斜率优化.其实是借鉴大牛大思路，Here，我只是抛砖引玉而已。其实这题可以作为模板题，斜率优化大抵如此吧。

    用这种方法我的代码跑了109ms。

测试数据：

Input:
4 1
4 5 1 2
4 2
4 5 1 2
5 3
1 2 1 2 1
6 4
7 5 3 6 8 9
10 3
1 4 2 7 5 6 8 5 6 9

OutPut:
17
2
92
15
187


C艹代码：

[cpp] view
plaincopy

  1. //四边形不等式  
  2. #include <stdio.h>  
  3. #include <string.h>  
  4. #define MAX 1100  
  5. #define INF (1<<30)  
  6.   
  7.   
  8. int n,m,sum[MAX],cost[MAX][MAX];  
  9. int arr[MAX],dp[MAX][MAX],s[MAX][MAX];  
  10.   
  11.   
  12. void Initial() {  
  13.   
  14.     int i, j, k;  
  15.   
  16.   
  17.     for (i = 1; i <= n; ++i)  
  18.         for (j = 1; j <= n; ++j)  
  19.             if (j < i) cost[i][j] = 0;  
  20.             else cost[i][j] = cost[i][j - 1] + arr[j] * (sum[j - 1] - sum[i - 1]);  
  21.     for (i = 0; i <= n; ++i) {  
  22.   
  23.         dp[i][0] = cost[1][i];  
  24.         s[i][0] = 0,s[n+1][i] = n;  
  25.     }  
  26. }  
  27. int Solve_DP() {  
  28.   
  29.     int i,j,k;  
  30.   
  31.   
  32.     for (j = 1; j <= m; ++j)  
  33.         for (i = n; i >= 1; --i) {  
  34.   
  35.             dp[i][j] = INF;  
  36.             for (k = s[i][j-1] ; k <= s[i+1][j]; ++k)  
  37.                 if (dp[k][j-1] + cost[k+1][i] < dp[i][j]) {  
  38.   
  39.                     s[i][j] = k;  
  40.                     dp[i][j] = dp[k][j-1] + cost[k+1][i];  
  41.                 }  
  42.         }  
  43.   
  44.   
  45.     return dp[n][m];  
  46. }  
  47.   
  48.   
  49. int main()  
  50. {  
  51.     int i,j,k;  
  52.   
  53.   
  54.     while (scanf("%d%d",&n,&m),n+m) {  
  55.   
  56.         for (i = 1; i <= n; ++i)  
  57.             scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];  
  58.   
  59.   
  60.         Initial();  
  61.         int ans = Solve_DP();  
  62.         printf("%I64d\n",ans);  
  63.     }  
  64. }  

[cpp] view
plaincopy

  1. //sum[i] = arr[1] + .. arr[i]^2  
  2. //sum2[i] = arr[1]^2 + .. arr[i]^2;  
  3. //dp[i][j] = min{dp[k][j-1] -sum[i] * sum[k] + (suma[k] - sum[k]^2)/2 + (sum[k]^2 - suma[k])/2};  
  4. //斜率优化二  
  5. #include <stdio.h>  
  6. #include <string.h>  
  7. #define MAX 1100  
  8. #define INF (1<<30)  
  9. #define int64 __int64//long long  
  10.   
  11.   
  12. struct point {  
  13.   
  14.     int64 x,y;  
  15. }pot[MAX];  
  16. int head,tail,qu[MAX];  
  17. int n,m,arr[MAX];  
  18. int64 sum[MAX],sum2[MAX],dp[MAX][MAX];  
  19.   
  20.   
  21. void Initial() {  
  22.   
  23.     for (int i = 1; i <= n; ++i) {  
  24.   
  25.         sum[i] = arr[i] + sum[i-1];  
  26.         sum2[i] = arr[i] * arr[i] + sum2[i-1];  
  27.         dp[i][0] = dp[i-1][0] + arr[i] * sum[i-1];  
  28.     }  
  29. }  
  30. int CheckIt(point p0,point p1,point p2) {  
  31.   
  32.     return (p0.x-p1.x) * (p0.y-p2.y) - (p0.y-p1.y) * (p0.x-p2.x) <= 0;  
  33. }  
  34. int NotBest(point p0,point p1,int k) {  
  35.   
  36.     return p0.y - k * p0.x > p1.y - k * p1.x;  
  37. }  
  38. int Solve_DP() {  
  39.   
  40.     int i,j,k;  
  41.   
  42.   
  43.     for (j = 1; j <= m; ++j) {  
  44.   
  45.         head = 0,tail = 0;  
  46.         qu[tail] = 0;  
  47.         for (i = j + 1; i <= n; ++i) {  
  48.   
  49.             pot[i].x = sum[i-1];  
  50.             pot[i].y = dp[i-1][j-1] + (sum[i-1] * sum[i-1] + sum2[i-1]) / 2;  
  51.             while (head <= tail - 1 &&  
  52.                     CheckIt(pot[qu[tail-1]],pot[qu[tail]],pot[i])) tail--;  
  53.   
  54.   
  55.             qu[++tail] = i;  
  56.             while (head + 1 <= tail &&  
  57.                     NotBest(pot[qu[head]],pot[qu[head+1]],sum[i])) head++;  
  58.             k = qu[head];  
  59.             //dp[i][j] = y - k * x + c  
  60.             dp[i][j] = pot[k].y - sum[i] * pot[k].x + (sum[i] * sum[i] - sum2[i]) / 2;  
  61.         }  
  62.     }  
  63.   
  64.   
  65.     return dp[n][m];  
  66. }  
  67. int GetInt() {  
  68.   
  69.     char ch = ' ';  
  70.     while (ch < '0' || ch > '9')  
  71.         ch = getchar();  
  72.     int x = 0;  
  73.     while (ch >= '0' && ch <= '9')  
  74.         x = x * 10 + ch - '0',ch = getchar();  
  75.     return x;  
  76. }  
  77.   
  78.   
  79. int main()  
  80. {  
  81.     int i,j,k;  
  82.   
  83.   
  84.     while (scanf("%d%d",&n,&m),n+m) {  
  85.   
  86.         for (i = 1; i <= n; ++i)  
  87.             scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];  
  88.   
  89.   
  90.         Initial();  
  91.         int ans = Solve_DP();  
  92.         printf("%d\n",ans);  
  93.     }  
  94. }  

[cpp] view
plaincopy

  1. //cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])  
  2. //dp[i][j]=dp[k][j-1]+cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])  
  3. //        =dp[k][j-1]-cost[1][k]+sum[k]^2-sum[i]*sum[k]+cost[1][i]  
  4. //斜率优化一   
  5. #include <stdio.h>  
  6. #include <string.h>  
  7. #define MAX 1100  
  8. #define INF (1<<30)  
  9.   
  10.   
  11. struct point {  
  12.   
  13.     int x,y;  
  14. }pot[MAX];  
  15. int head,tail,qu[MAX];  
  16. int n,m,arr[MAX],cost[MAX];  
  17. int sum[MAX],sum2[MAX],dp[MAX][MAX];  
  18.   
  19.   
  20. void Initial() {  
  21.   
  22.     for (int i = 1; i <= n; ++i) {  
  23.   
  24.         sum[i] = arr[i] + sum[i-1];  
  25.         cost[i] = cost[i-1] + arr[i] * sum[i-1];  
  26.         dp[i][0] = cost[i];  
  27.     }  
  28. }  
  29. int CheckIt(point p0,point p1,point p2) {  
  30.   
  31.     return (p0.x-p1.x) * (p0.y-p2.y) - (p0.y-p1.y) * (p0.x-p2.x) <= 0;  
  32. }  
  33. int NotBest(point p0,point p1,int k) {  
  34.   
  35.     return p0.y - k * p0.x > p1.y - k * p1.x;  
  36. }  
  37. int Solve_DP() {  
  38.   
  39.     int i,j,k;  
  40.   
  41.   
  42.     for (j = 1; j <= m; ++j) {  
  43.   
  44.         head = 0,tail = 0;  
  45.         qu[tail] = 0;  
  46.         for (i = j + 1; i <= n; ++i) {  
  47.   
  48.             pot[i].x = sum[i-1];  
  49.             pot[i].y = dp[i-1][j-1] - cost[i-1] + sum[i-1] * sum[i-1];  
  50.             while (head <= tail - 1 &&  
  51.                     CheckIt(pot[qu[tail-1]],pot[qu[tail]],pot[i])) tail--;  
  52.   
  53.   
  54.             qu[++tail] = i;  
  55.             while (head + 1 <= tail &&  
  56.                     NotBest(pot[qu[head]],pot[qu[head+1]],sum[i])) head++;  
  57.             k = qu[head];  
  58.             //dp[i][j] = y - k * x + c  
  59.             dp[i][j] = pot[k].y - sum[i] * pot[k].x + cost[i];  
  60.         }  
  61.     }  
  62.   
  63.   
  64.     return dp[n][m];  
  65. }  
  66.   
  67.   
  68. int main()  
  69. {  
  70.     int i,j,k;  
  71.   
  72.   
  73.     while (scanf("%d%d",&n,&m),n+m) {  
  74.   
  75.         for (i = 1; i <= n; ++i)  
  76.             scanf("%d",&arr[i]),sum[i] = arr[i] + sum[i-1];  
  77.   
  78.   
  79.         Initial();  
  80.         int ans = Solve_DP();  
  81.         printf("%d\n",ans);  
  82.     }  
  83. } 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞