uva 12524

题意：沿河有n个点，每个点有w的东西，有一艘船从起点出发，沿途可以装运东西和卸载东西，船的容量无限，每次把wi的东西从x运到y的花费为(y-x)*wi;

问把n个点的东西合并成k个的最小花费；

分析：设dp[j][i]表示把前i个点的东西合并成j个点的最小花费，那么dp[j][i] = min( dp[j-1][k] + w[k+1]*(x[i] - x[k+1]) + w[k+2]*(x[i] - x[k+2]) + ... + w[i] * (x[i] - x[i]));

设sw[i] = w[1] + w[2] + ...+w[i];

swx[i] = w[1]*x[1] + w[2]*x[2] + ... + w[i]*x[i];

那么 dp[j][i] = min( dp[j-1][k] + x[i] * (sw[i] - sw[k]) - (swx[i] - swx[k]) , 0<k<i );

显然dp[j][i] = -x[i] * sw[k] + swx[k] + dp[j-1][k] + x[i] * sw[i] - swx[i];

斜率为 x[i];

x = sw[k];  y = swx[k] + dp[j-1][k];然后套模板；

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
             
            
           
          
         
        
       
      

 

 

cf319C 

1 /* 2  题意：有n课树要砍，每次只能砍1个单位的长度，每次砍完后都要花费已经砍完的id最大的树的bi时间充电，a1 = 1;     3  并且 bn = 0; 问最少花多少时间把树砍完； 4  5  设DP[i]表示使当前已经砍完的树的最大ID是i的最小花费 6  方程:DP[i] = DP[j] + b[j] + (a[i]-1)*b[j];    //最后一棵树只需要a[i]-1次，第一b[j]表示补上上一棵树的最后一次； 7  8  然后就是标准的斜率DP; 9  DP[i] = DP[j] + a[i]*b[j];10  设 b[j] = x[j]; DP[j] = y[j];11  G = a[i]*x[j]+y[j];12  因为x[j]是单调递减的，y[j]是单调递增的，a[i]是单调递增的；13  所以满足条件；14  套一下模板就好；15  16  trick： 在做Cross()时会爆LL,然后又因为我那样写u.x,v.x都是负数，移项要变符号，17  然后太懒，没有自己造例子，样例一直可以跑出，花了一个晚上找BUG,教训啊！！18 19  */20 #include
     
      21 #include
      
       22 #include
       
        23 #include
        
         24 #include
         
          25 #include
          
           26 #include
           
            27 using namespace std;28 typedef long long LL;29 const int N=100000+10;30 struct Point{31 LL x,y;32 Point (LL a=0,LL b=0):x(a),y(b){}33 Point operator - (const Point &p)const{34 return Point(x-p.x,y-p.y);35 }36 };37 const double eps = 1e-10;38 int dcmp(double x){39 return x < -eps ? -1 : x > eps;40 }41 LL Cross(const Point &u,const Point &v){42 if (dcmp(u.x*1.0/v.x - u.y*1.0/v.y) <= 0) return 1;43 return -1;44 }45 Point q[N];46 int head,tail;47 void init(){48 head = 1; tail = 0;49 }50 void push(const Point &u){51 while (head < tail && Cross(q[tail]-q[tail-1], u-q[tail-1]) >= 0 ) tail--;52 q[++tail] = u;53 }54 void pop(const LL &k){55 while (head < tail && k*q[head].x + q[head].y >= k*q[head+1].x + q[head+1].y ) head++;56 }57 int n;58 LL a[N],b[N];59 LL dp[N];60 void solve(){61 init();62 dp[1] = 0; push(Point(b[1],0));63 for (int i = 2; i <= n; i++) {64 pop(a[i]);65 dp[i] = a[i] * q[head].x + q[head].y;66 push(Point(b[i],dp[i]));67 }68 printf("%I64d\n",dp[n]);69 }70 int main(){71 freopen("in.txt","r",stdin);72 while (~scanf("%d",&n)){73 for (int i = 1; i <= n; i++) {74 scanf("%I64d",a+i);75 }76 for (int i = 1; i <=n; i++) {77 scanf("%I64d",b+i);78 }79 solve();80 81 82 }83 return 0;84 }
           
          
         
        
       
      
     

 

 cf311 B

1 /* 2  题意：有直线上n个地点，m只cat，p个喂养人，cat会在ti到达hi，喂养人从地点1 3  任意时间出发，如果碰到已经到达的CAT就照顾，问怎么安排喂养人 4  使所有CAT被照顾到且，cat等待的时间最少； 5  6  sum_di[i]表示 地点i到地点1的距离，那么 val[j] = ti[j] - sum_di[hi[j]就表示对cat j 7  喂养人最早的出发时间； 8  sort(val); 那么题意就是讲val[]至多分成p段，每段的花费为： 9  设该段为[i,j]，w = val[j]*(j-i+1)- (sum[j] - sum[j-1]);10 11  设DP[j][i]表示 前i个值分成j段的最小花费12  方程:DP[j][i] = DP[j-1][k] + val[i]*(i-k) - (sum[i]-sum[k]);13  很明显可以化成斜率的DP的模式；14  x[k] = k;15  y[k] = sum[k] + dp[k];16  G = -a[i]*x[k] + y[k]；17 18 trick :人出发的时间可以是负的，19  */20 #include
     
      21 #include
      
       22 #include
       
        23 #include
        
         24 #include
         
          25 #include
          
           26 using namespace std;27 const int N=100000+10;28 typedef long long LL;29 struct Point{30 LL x,y;31 Point (LL a=0,LL b=0):x(a),y(b){}32 Point operator - (const Point &p)const{33 return Point (x-p.x, y-p.y);34 }35 };36 LL Cross(const Point &u,const Point &v){37 return u.x*v.y - u.y*v.x;38 }39 40 Point q[N];41 int head,tail;42 void init(){43 head = 1; tail = 0;44 }45 void push(const Point &u){46 while (head < tail && Cross(q[tail]-q[tail-1],u-q[tail-1]) <= 0) tail--;47 q[++tail] = u;48 }49 void pop(const LL &k){50 while (head < tail && k*q[head].x + q[head].y >= k*q[head+1].x+q[head+1].y) head++;51 }52 int n,m,p;53 LL di[N],sum_di[N];54 LL sum[N],hi[N],ti[N],val[N];55 void init_val(){56 for (int i = 1; i<=m ;i++){57 val[i] = ti[i] - sum_di[hi[i]];58 } 59 sort(val+1,val+m+1);60 sum[0] = 0;61 for (int i = 1; i<=m; i++) {62 sum[i] = sum[i-1] + val[i];63 }64 /* for (int i =1; i<=m; i++) {65 cout << val[i] << " ";66 }cout<
          
         
        
       
      
     

 

 hdu 3669

1 /*  2 题意：n个A矩形，至多在墙上挖M个B矩形，每个B矩形的花费是矩形的面积，且每个B矩形不能重叠，  3        使所有A矩形都能通过，（A矩形不能旋转），问最小的花费；  4   5 按照wi从大到小，如果wi相等，则按hi从大到小排，这样对于wi相同的矩形，只要hi最高的能通过，其他  6 的肯定能通过，这样可以预处理出必要的矩形；  7   8 这样问题就变成，给你wi递减，hi递增的矩形序列，至多分成M段，没段的花费为  9 w[i,j] = mat[i].wi*mat[j].hi; 10  11 设DP[j][i]表示将前i个矩形划分成j段的最小花费； 12 DP[j][i] = DP[j-1][k] + w[k,i]; 13  14 很标准的斜率DP； 15  16 注意： 常数很大，写在结构体里就T了，还有就是能不用LL的就不要用LL， 17 用LL的常数也很大， 18 还有就是一个可以”优化“的，就是if dp[j][n] > ret then break;  标记为“>.<”的那行； 19 但是不知道是不是对的 20 */ 21 #include
     
       22 #include
      
        23 #include
       
         24 #include
        
          25 #include
         
           26 #include
          
            27 #include
           
             28 #include
            
              29 using namespace std; 30 const int N=50000+10; 31 typedef long long LL; 32 struct Point{ 33 int x; 34 LL y; 35 Point (int a=0,LL b=0):x(a),y(b){} 36 Point operator - (const Point &p) const{ 37 return Point(x-p.x,y-p.y); 38 } 39 }; 40 typedef Point Vector; 41 inline LL Cross(const Vector &u,const Vector &v){ 42 return (LL)u.x*v.y - (LL)u.y*v.x; 43 } 44 struct rec{ 45 int w,h; 46 bool operator < (const rec &p)const{ 47 return w>p.w || (w==p.w && h>p.h); 48 } 49 }mat[N]; 50 int n,M; 51 Point q[N]; 52 int head,tail; 53 /* 54 struct dequeue{ 55 Point q[N]; 56 int head,tail; 57 void init(){ 58 head = 1; tail = 0; 59 } 60 void push(const Point &u){ 61 while (head < tail && Cross(q[tail]-q[tail-1],u-q[tail-1]) >= 0 ) tail--; 62 q[++tail] = u; 63 } 64 Point pop(const LL &k){ 65 while (head < tail && k*q[head].x + q[head].y >= k*q[head+1].x + q[head+1].y ) head++; 66 return q[head]; 67 } 68 }H; 69 */ 70 LL dp[2][N]; 71 void solve(){ 72 73 sort(mat+1,mat+n+1); 74 int tn=1; 75 for (int i=2;i<=n;i++){ 76 if (mat[tn].w!=mat[i].w && mat[tn].h < mat[i].h) mat[++tn] = mat[i]; 77 } 78 n = tn; 79 80 LL ret = -1; 81 int pos=0; 82 dp[pos][0] = 0; 83 for (int i=1;i<=n;i++){ 84 dp[pos][i]=(LL)mat[1].w*mat[i].h; 85 } 86 ret = dp[pos][n]; 87 for (int j=2;j<=M;j++){ 88 head = 1; tail = 0; 89 for (int i=1;i<=n;i++){ 90 Point u=Point(mat[i].w,dp[pos][i-1]); 91 while (head < tail && Cross(q[tail]-q[tail-1],u-q[tail-1]) >= 0 ) tail--; 92 q[++tail] = u; 93 while (head < tail && (LL)q[head].x*mat[i].h + q[head].y >= (LL)q[head+1].x*mat[i].h + q[head+1].y ) 94 head++; 95 96 dp[pos^1][i] = (LL)q[head].x*mat[i].h + q[head].y; 97 } 98 99 pos ^= 1; dp[pos][0] = 0;100 if (dp[pos][n] < ret) ret = dp[pos][n];101 //else break； >.<102 }103 printf("%I64d\n",ret);104 }105 int main(){106 //freopen("in.txt","r",stdin);107 while (~scanf("%d%d",&n,&M)){108 for (int i=1;i<=n;i++){109 scanf("%d%d",&mat[i].w,&mat[i].h);110 }111 solve();112 }113 return 0;114 }
            
           
          
         
        
       
      
     

 

hdu 3725

1 /*  2 题意：happy Farm，偷菜，且只能按照价值从大到小开始偷（一般斜率DP都是这样，有一定的顺序，然后就是分段了）  3 每个蔬菜有两个值ai,di，可以刷新M次，每次刷新后DOG的anger值变成0;  4   5 抽象一下：给你一个序列，至多分成M段，每段的花费是w[i,j];  6 在花费小于ti的情况下，使每段sum_di的最大值最小；  7   8 w[i+1,j] = a[i+1]*1 +　a[i+2]*2 + ... + a[j]*(j-i+1);  9  10 最大值最小，很容易让人想到二分最大值m，然后判断是否满足； 11  12 现在问题变成：每段sum_di的值不超过m,问是否存在方案使得花费小于ti； 13  14 Ti[i] = a[1]*1 + a[2]*2 + ... + a[i]*i; 15 sum[i] = a[1] + a[2] + ... + a[i]; 16 w[i+1,j] = Ti[j] - Ti[i] - sum[i]*(j-i); 17  18 dp[j][i]表前i个蔬菜，分成j段，每段sum_di满足要求下的最小花费； 19 dp[j[i] = dp[j-1][k] + w[k,i]; 20  21 显然也是一个斜率DP模型； 22  23 因为每段加了一个sum_di不能超过m的要求，所以在POP时还要POP掉不能满足条件的点 24 这就有可能H.q[]里一个点也没有，anger[i]本身大于m,所以我们在操作时要判断一下， 25 同样在PUSH时也是，不需要把那些不满足的点push进去； 26  27 初始化，和队列的边界问题我想是写斜率DP的唯一要注意一下的地方； 28  29 */ 30 #include
     
       31 #include
      
        32 #include
       
         33 #include
        
          34 #include
         
           35 #include
          
            36 #include
           
             37 #include
            
              38 using namespace std; 39 const int N=30000+10; 40 typedef long long LL; 41 struct Point{ 42 LL x,y; 43 Point (LL a=0,LL b=0):x(a),y(b){} 44 Point operator - (const Point &p)const{ 45 return Point(x - p.x, y - p.y); 46 } 47 }; 48 LL sum[N],Ti[N],ti; 49 int n,M,r,anger[N]; 50 typedef Point Vector; 51 LL Cross(const Vector &u,const Vector &v){ 52 return u.x*v.y - u.y*v.x; 53 } 54 struct dequeue{ 55 Point q[N]; 56 int head,tail; 57 void init(){ 58 head = 1; tail = 0; 59 } 60 void push(const Point &u){ 61 while (head < tail && Cross(q[tail] - q[tail-1],u - q[tail-1]) <= 0) 62 tail--; 63 q[++tail] = u; 64 } 65 void pop(int k,int i,int w){ 66 while (head <= tail && anger[i] - anger[q[head].x] > w) head++; 67 while (head < tail && -k*q[head].x + q[head].y >= -k*q[head+1].x + q[head+1].y) head++; 68 69 } 70 }H; 71 72 struct vegetable{ 73 int vi,ai; 74 LL di; 75 vegetable(int v=0,int a=0,LL d=0):vi(v),ai(a),di(d){} 76 bool operator < (const vegetable &p)const{ 77 return vi>p.vi; 78 } 79 void input(){ 80 scanf("%d%d%I64d",&vi,&ai,&di); 81 } 82 void output(){ 83 cout<< vi <<" "<< ai <<" "<< di << endl; 84 } 85 86 }vg[N]; 87 88 void init(){ 89 sort(vg+1,vg+n+1); 90 anger[0] = sum[0] = Ti[0] = 0; 91 for (int i=1;i<=n;i++) { 92 sum[i]=sum[i-1]+vg[i].di; 93 Ti[i]=Ti[i-1]+i*vg[i].di; 94 anger[i] = anger[i-1] + vg[i].ai; 95 } 96 /* 97 for (int i=0;i<=n;i++) cout<
             
              <<" ";cout<
              
                ti || ret == -1) return 0;130 return 1;131 }132 void solve(int l,int r){133 init();134 int ret=-1;135 while (r>=l){136 int m=(l+r)>>1;137 if (check(m)){138 ret=m; r=m-1;139 }else l=m+1;140 }141 if (ret == -1) printf("I have no idea\n");142 else printf("%d\n",ret);143 }144 int main(){145 146 freopen("in.txt","r",stdin);147 int T; scanf("%d",&T);148 while (T--){149 scanf("%d%d%d%I64d",&n,&M,&r,&ti);150 int allai = 0;151 for (int i=1;i<=n;i++){152 vg[i].input();153 allai += vg[i].ai;154 }155 solve(1,allai);156 }157 return 0;158 }