博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
斜率优化DP
阅读量：7254 次
发布时间：2019-06-29

本文共 11476 字，大约阅读时间需要 38 分钟。

hdu 2993 MAX Average Problem

这题都整死我了，代码基本上和别人AC的都快一样了还是不对。郁闷死了快。。最后终于发现了错误点自判断斜率时y1*x2 <= y2*x1 如果用整型就会超数据类型肯定会错，而上边的用整型可以过，不过最好用实型因为毕竟k的大小不确定。。。这题的详细解释 例2 这里在转到0-n个点求斜率的时候不好理解。

数形结合以形住树。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 100007#define N 100007using namespace std;int q[N],sum[N];double max(double a,double b){ return a > b ? a:b;}int GetInt(){ char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); int num = 0; while (ch >= '0' && ch <= '9') { num = num*10 + ch - '0'; ch = getchar(); } return num;}int main(){ //freopen("data.in","r",stdin); int n,i,k; while (~scanf("%d%d",&n,&k)) { sum[0] = 0; for (i = 1; i <= n; ++i) { int x = GetInt(); sum[i] = sum[i - 1] + x; } int front = 0,tail = 0; q[0] = 0; double ans = 0; for (i = k; i <= n; ++i) { int now = i - k; while (tail > front) { int y1 = sum[q[tail]] - sum[q[tail - 1]]; int x1 = q[tail] - q[tail - 1]; int y2 = sum[now] - sum[q[tail]]; int x2 = now - q[tail]; if (y1*x2 >= y2*x1) tail--; else break; } q[++tail] = now; while(front
                
                  ans) ans = tmp; } printf("%.2lf\n",ans); } return 0;}

 

 

hdu  3507 Print Article

题意：

给定长度为n的整数序列，

对他进行划分，每一段的花费为上述公式:假设从i到j为一段划分则花费为 (∑Ck)^2 + m ， i<=k<=j。求一个划分使花费最小。

思路：

这里参考别人的思路，给出个人感觉讲解比较好的连接：

代码参考：

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 100007#define N 500007using namespace std;//freopen("din.txt","r",stdin);struct point{ int x,y;}pot[N];int sum[N],q[N];ll dp[N];int n,m;int cross(int x1,int y1,int x2,int y2){ return x1*y2 - x2*y1;}int det(point a,point b,point c){ return cross(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);}bool CheckIt(int x,int y,int z)//叉积判断点在线段的方向{ int mk = det(pot[x],pot[y],pot[z]); if (mk <= 0) return true; else return false;}bool NotBest(int a,int b,int k){ point p0 = pot[a], p1 = pot[b]; if (pot[a].y - k*pot[a].x >= pot[b].y - k*pot[b].x) return true; else return false;}int GetInt()//开挂输入{ char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); int num = 0; while (ch >= '0' && ch <= '9') { num = num*10 + ch - '0'; ch = getchar(); } return num;}int main(){ //freopen("din.txt","r",stdin); int i; while (~scanf("%d%d",&n,&m)) { sum[0] = 0; for (i = 1; i <= n; ++i) { //scanf("%d",&sum[i]); sum[i] = GetInt(); sum[i] += sum[i - 1];//累加和 } int front = 0,tail = 0; pot[0].x = pot[0].y = 0;//出事化原点 q[0] = 0; for (i = 1; i <= n; ++i) { pot[i].x = sum[i - 1]; pot[i].y = dp[i - 1] + sum[i - 1]*sum[i - 1];//记录每个状态的x,y; while (front + 1 <= tail && CheckIt(q[tail - 1],q[tail],i)) tail--;//删除不可能为最优的上凸点 q[++tail] = i; while (front + 1 <= tail && NotBest(q[front],q[front + 1],2*sum[i])) front++;//将在下凸折线不是最有的点删除 int k = q[front]; dp[i] = pot[k].y - 2*sum[i]*pot[k].x + sum[i]*sum[i] + m;//获取最优值 } printf("%I64d\n",dp[n]); } return 0;}

 

hdu 3408  Division

题意：

给你一个含有n个数的集合，让你划分成M个子集，每个集合里面的(MAX - MIN)^2为这个集合的花费，求总的花费最小。

思路：

首先我们要经整体排序

我们可以得到状态转移方程dp[i][j]表示以j结尾将序列划分成i块的最小花费则有dp[i][j] = min(dp[i - 1][k] + (a[j] - a[k + 1])*(a[j] - a[k + 1]));这样求的话复杂度O(n*m*m)肯定会超时。所以要优化，我们把方程拆开得到dp[i][j] = dp[i - 1][k] +　a[j]^2 + a[k + 1]^ - 2*a[j]*a[k + 1];令y = dp[i - 1][k] + a[k + 1]^2 ; x = a[k + 1].

得到 dp[i][j] = y - 2*a[j]*x + a[j]^2;

则套用斜率优化即可。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 5007#define N 10007using namespace std;//freopen("din.txt","r",stdin);struct point{ int x; int y;}pot[N];int dp[M][N];int n,m,a[N],q[N];int cmp(int x,int y){ return x < y;}int cross(int x1,int y1,int x2,int y2){ return x1*y2 - x2*y1;}int det(point a,point b,point c){ return cross(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);}int GetInt(){ char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); int num = 0; while (ch >= '0' && ch <= '9') { num = num*10 + ch - '0'; ch = getchar(); } return num;}bool CheckIt(int x,int y,int z){ int mk = det(pot[x],pot[y],pot[z]); if (mk <= 0) return true; else return false;}bool NotBest(int a,int b,int k){ if (pot[a].y - k*pot[a].x <= pot[b].y - k*pot[b].x) return true; else return false;}int main(){ //freopen("din.txt","r",stdin); int i,j,t,k; int cas = 1; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); for (i = 1; i <= n; ++i) scanf("%d",&a[i]); sort(a + 1,a + 1 + n,cmp); for (i = 1; i <= n; ++i)//出事划分成一个集合的 dp[1][i] = (a[i] - a[1])*(a[i] - a[1]); pot[0].x = pot[0].y = 0; q[0] = 0; for (i = 2; i <= m; ++i)//枚举划分的大小 { int front = 0,tail = 0; for (j = i; j <= n; ++j)//枚举可能的结束点 { pot[j].x = a[j]; pot[j].y = dp[i - 1][j - 1] + a[j]*a[j]; while (front + 1 <= tail && CheckIt(q[tail - 1],q[tail],j)) tail--; q[++tail] = j; while (front + 1 <= tail && NotBest(q[front + 1],q[front],2*a[j])) front++; k = q[front]; dp[i][j] = pot[k].y - 2*a[j]*pot[k].x + a[j]*a[j]; } } printf("Case %d: %d\n",cas++,dp[m][n]); } return 0;}

 

hdu 4258 Covered Walkway

 和上边的两道题目基本上一样，都是划分的题目。

题意：

给你x坐标上的n个点，让你让你两点连线将所有点覆盖，假设我们在a[i]到a[j]连线，则i-j的点都已经覆盖并且这一段的费用为(j - i)^2,求把所有点覆盖后的最小花费。

思路：

由题可得状态转移方程dp[i] = min(dp[j] + (a[i] - a[j + 1])^2 + c) (1<=j < i) 将方程展开后记得

dp[i] = dp[j] + a[j + 1]^2 + a[i]^2 - 2*a[i]*a[j + 1] + c; 令y = dp[j] + a[j + 1]^2 ; x = a[j + 1]; 则有dp[i] = y - 2*a[i]*x + a[i]^2 + c;

套用斜率优化即可。注意数据类型的处理，这里因为超了数据类型错了一次。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 5007#define N 1000007using namespace std;//freopen("din.txt","r",stdin);struct point{ ll x,y;}pot[N];ll dp[N];ll a[N],c;int q[N];int n;ll cross(ll x1,ll y1,ll x2,ll y2){ return x1*y2 - x2*y1;}ll det(point a,point b,point c){ return cross(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);}bool CheckIt(int x,int y,int z){ ll mk = det(pot[x],pot[y],pot[z]); if (mk <= 0) return true; else return false;}bool NotBest(int a,int b,ll k){ if (pot[a].y - k*pot[a].x <= pot[b].y - k*pot[b].x) return true; else return false;}ll GetInt(){ char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); ll num = 0; while (ch >= '0' && ch <= '9') { num = num*10 + ch - '0'; ch = getchar(); } return num;}int main(){ //freopen("din.txt","r",stdin); int i; while (~scanf("%d%I64d",&n,&c)) { if (!n && !c) break; for (i = 1; i <= n; ++i) a[i] = GetInt(); //scanf("%I64d",&a[i]); int front = 0,tail = 0; pot[0].x = pot[0].y = 0; q[0] = 0; for (i = 1; i <= n; ++i) { pot[i].x = a[i]; pot[i].y = dp[i - 1] + a[i]*a[i]; while (front + 1 <= tail && CheckIt(q[tail - 1],q[tail],i)) tail--; q[++tail] = i; while (front + 1 <= tail && NotBest(q[front + 1],q[front],2*a[i])) front++; int k = q[front]; dp[i] = pot[k].y - 2*a[i]*pot[k].x + a[i]*a[i] + c; //if (i == 1) printf("%I64d %I64d %I64d %I64d %d\n",pot[i].x,pot[i].y,dp[1],a[i],c); } printf("%I64d\n",dp[n]); } return 0;}

 

hdu 2829  Lawrence

 

基本上和上几个题类似：

题意：

Lawrence要建一条铁路，铁路包括一些收费站（这里描述为一些点，对应着有自己的vale），还有连接两点的线，这条铁路的花费计算方法为：

4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.

由于资金材料的限制只能毁掉一些线，使的耗费减小.给定n个点，以及要炸掉m个边求如何炸才能得到最小耗费，输出最小耗费。

思路：

首先我们得到状态转移方程dp[i][j]表示以i结尾炸掉j条路线的最小耗费。则有

dp[i][j] = min(dp[k][j - 1] + cost[k + 1][i]) (1<=k<i). cost[i][j]表示i到j这串数字的乘积和,sum[i]表示1到i为止这些数字的和

cost[1][i] = cost[1][k] + cost[k + 1][i] + sum[k]*(sum[i] - sum[k]);

==>cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])

==>dp[i][j]=dp[k][j-1]+cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])

==>dp[k][j-1]-cost[1][k]+sum[k]^2-sum[i]*sum[k]+cost[1][i]

==>由于sum[i]是与i有关的常量，所以很明显，斜率k=sum[i]，

设y=dp[k][j-1]-cost[1][k]+sum[k]^2
那么dp[i][j]=y-k*x+cost[1][i]

到这一步就可以套用斜率优化了。

View Code 
#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 5007#define N 1007using namespace std;//freopen("din.txt","r",stdin);int n,m;int q[N];struct point{ ll x,y;}pot[N];ll cost[N],sum[N],a[N],dp[N][N];ll cross(ll x1,ll y1,ll x2,ll y2){ return x1*y2 - x2*y1;}ll det(point a,point b,point c){ return cross(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);}bool CheckIt(int x,int y,int z){ ll mk = det(pot[x],pot[y],pot[z]); if (mk <= 0) return true; else return false;}bool NotBest(int a,int b,ll k){ if (pot[a].y - k*pot[a].x <= pot[b].y - k*pot[b].x) return true; else return false;}ll solve_DP(){ int i,j; int front,tail; pot[0].x = pot[0].y = 0; q[0] = 0; for (j = 1; j <= m; ++j) { front = tail = 0; for (i = j + 1; i <= n; ++i) { pot[i].x = sum[i - 1]; pot[i].y = dp[i - 1][j - 1] - cost[i - 1] + sum[i - 1]*sum[i -1]; while (front + 1 <= tail && CheckIt(q[tail - 1],q[tail],i)) tail--; q[++tail] = i; while (front + 1 <= tail && NotBest(q[front + 1],q[front],sum[i])) front++; int k = q[front]; dp[i][j] = pot[k].y - sum[i]*pot[k].x + cost[i]; } } return dp[n][m];}ll GetInt(){ char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); ll num = 0; while (ch >= '0' && ch <= '9') { num = num*10 + ch - '0'; ch = getchar(); } return num;}int main(){ //freopen("din.txt","r",stdin); int i; while (~scanf("%d%d",&n,&m)) { if (!n && !m) break; sum[0] = 0; for (i = 1; i <= n; ++i) { //scanf("%I64d",&a[i]); a[i] = GetInt(); sum[i] = sum[i - 1] + a[i]; } cost[0] = 0; for (i = 1; i <= n; ++i) { cost[i] = cost[i - 1] + sum[i - 1]*a[i]; dp[i][0] = cost[i];//初始化 } /* for (i = 1; i <= n; ++i) printf("%I64d ",cost[i]); puts("");*/ ll ans = solve_DP(); printf("%I64d\n",ans); } return 0;}

 

 

 

转载地址：http://ijzdm.baihongyu.com/

你可能感兴趣的文章
位操作：BitVector32结构 z
查看>>
初学java之菜单条，菜单，菜单项的设置
查看>>
Java 集合
查看>>
Sql Server 2008R2版本中有关外键Foreign的使用
查看>>
mysqldump导入导出mysql数据库
查看>>
js小记 function 的 length 属性
查看>>
jQuery 遍历函数
查看>>
Android的消息机制: Message/MessageQueue/Handler/Looper
查看>>
ASP.NET MVC学习系列(一)-WebAPI初探
查看>>
Gson简要使用笔记
查看>>
windows批量创建用户
查看>>
category使用 objc_setAssociatedObject/objc_getAssociatedObject 实现添加属性
查看>>
"org.jboss.netty.internal.LoggerConfigurator".DESCRIBED is already registered 的解决办法
查看>>
字符串交替打印 操作方法
查看>>
Ubuntu 用vsftpd 配置FTP服务器
查看>>
java中的io系统详解(转)
查看>>
iOS开发- UICollectionView详解+实例
查看>>
android 从零单排 第一期 按键显示helloworld
查看>>
Get buck-boost performance from a boost regulator
查看>>
串行通信------字符串发送和十六进制发送
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-15 16:21:28   当前IP: 3.16.129.167   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我