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];然后套模板；
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pbk push_back
#define mk make_pair
using namespace std;
typedef long long LL;
const int N = +;
const double eps = 1e-;
inline int dcmp(double x) {
return x < -eps ? - : x > eps;
}
LL x[N],sw[N],swx[N],w[N];
int n,k;
LL dp[N][N];
struct Point{
LL x,y;
Point (LL x = , LL y = ):x(x),y(y){}
Point operator - (const Point &p)const{
return Point(x - p.x, y - p.y);
}
LL operator * (const Point &p)const{
return x * p.y - y * p.x;
}
};
struct dequeue{
int head,tail;
Point q[N];
void init(){
head = ; tail = ;
}
void push(const Point &u){
while (head < tail && (q[tail] - q[tail - ]) * (u - q[tail - ]) <= ) tail--;
q[++tail] = u;
}
Point pop(const LL &k) {
while (head < tail && k*q[head].x + q[head].y >= k*q[head+].x + q[head+].y) head++;
return q[head];
}
}H;
void solve(){
sw[] = swx[] = ;
for (int i = ; i <= n; i++) {
sw[i] = sw[i-] + w[i];
swx[i] = swx[i-] + w[i]*x[i];
}
memset(dp,,sizeof(dp));
for (int i = ; i <= n; i++) {
dp[][i] = x[i]*sw[i] - swx[i];
}
for (int j = ; j <= k; j++){
H.init(); H.push(Point(sw[j-],swx[j-] + dp[j-][j-]));
for (int i = j; i <= n; i++) {
Point p = H.pop(-x[i]);
dp[j][i] = x[i]*sw[i] - swx[i] - x[i] * p.x + p.y;
H.push(Point(sw[i],swx[i] + dp[j-][i]));
}
}
printf("%lld\n",dp[k][n]); }
int main(){
while (~scanf("%d%d",&n,&k)) {
for (int i = ; i <= n; i++) {
scanf("%lld%lld",&x[i],&w[i]);
}
solve();
}
return ;
}
cf319C
http://codeforces.com/contest/319/problem/C
/*
题意：有n课树要砍，每次只能砍1个单位的长度，每次砍完后都要花费已经砍完的id最大的树的bi时间充电，a1 = 1;
并且 bn = 0; 问最少花多少时间把树砍完； 设DP[i]表示使当前已经砍完的树的最大ID是i的最小花费
方程:DP[i] = DP[j] + b[j] + (a[i]-1)*b[j]; //最后一棵树只需要a[i]-1次，第一b[j]表示补上上一棵树的最后一次； 然后就是标准的斜率DP;
DP[i] = DP[j] + a[i]*b[j];
设 b[j] = x[j]; DP[j] = y[j];
G = a[i]*x[j]+y[j];
因为x[j]是单调递减的，y[j]是单调递增的，a[i]是单调递增的；
所以满足条件；
套一下模板就好； trick： 在做Cross()时会爆LL,然后又因为我那样写u.x,v.x都是负数，移项要变符号，
然后太懒，没有自己造例子，样例一直可以跑出，花了一个晚上找BUG,教训啊！！ */
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=+;
struct Point{
LL x,y;
Point (LL a=,LL b=):x(a),y(b){}
Point operator - (const Point &p)const{
return Point(x-p.x,y-p.y);
}
};
const double eps = 1e-;
int dcmp(double x){
return x < -eps ? - : x > eps;
}
LL Cross(const Point &u,const Point &v){
if (dcmp(u.x*1.0/v.x - u.y*1.0/v.y) <= ) return ;
return -;
}
Point q[N];
int head,tail;
void init(){
head = ; tail = ;
}
void push(const Point &u){
while (head < tail && Cross(q[tail]-q[tail-], u-q[tail-]) >= ) tail--;
q[++tail] = u;
}
void pop(const LL &k){
while (head < tail && k*q[head].x + q[head].y >= k*q[head+].x + q[head+].y ) head++;
}
int n;
LL a[N],b[N];
LL dp[N];
void solve(){
init();
dp[] = ; push(Point(b[],));
for (int i = ; i <= n; i++) {
pop(a[i]);
dp[i] = a[i] * q[head].x + q[head].y;
push(Point(b[i],dp[i]));
}
printf("%I64d\n",dp[n]);
}
int main(){
freopen("in.txt","r",stdin);
while (~scanf("%d",&n)){
for (int i = ; i <= n; i++) {
scanf("%I64d",a+i);
}
for (int i = ; i <=n; i++) {
scanf("%I64d",b+i);
}
solve(); }
return ;
}
cf311 B
http://codeforces.com/contest/311/problem/B
/*
题意：有直线上n个地点，m只cat，p个喂养人，cat会在ti到达hi，喂养人从地点1
任意时间出发，如果碰到已经到达的CAT就照顾，问怎么安排喂养人
使所有CAT被照顾到且，cat等待的时间最少； sum_di[i]表示 地点i到地点1的距离，那么 val[j] = ti[j] - sum_di[hi[j]就表示对cat j
喂养人最早的出发时间；
sort(val); 那么题意就是讲val[]至多分成p段，每段的花费为：
设该段为[i,j]，w = val[j]*(j-i+1)- (sum[j] - sum[j-1]); 设DP[j][i]表示 前i个值分成j段的最小花费
方程:DP[j][i] = DP[j-1][k] + val[i]*(i-k) - (sum[i]-sum[k]);
很明显可以化成斜率的DP的模式；
x[k] = k;
y[k] = sum[k] + dp[k];
G = -a[i]*x[k] + y[k]； trick :人出发的时间可以是负的，
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=+;
typedef long long LL;
struct Point{
LL x,y;
Point (LL a=,LL b=):x(a),y(b){}
Point operator - (const Point &p)const{
return Point (x-p.x, y-p.y);
}
};
LL Cross(const Point &u,const Point &v){
return u.x*v.y - u.y*v.x;
} Point q[N];
int head,tail;
void init(){
head = ; tail = ;
}
void push(const Point &u){
while (head < tail && Cross(q[tail]-q[tail-],u-q[tail-]) <= ) tail--;
q[++tail] = u;
}
void pop(const LL &k){
while (head < tail && k*q[head].x + q[head].y >= k*q[head+].x+q[head+].y) head++;
}
int n,m,p;
LL di[N],sum_di[N];
LL sum[N],hi[N],ti[N],val[N];
void init_val(){
for (int i = ; i<=m ;i++){
val[i] = ti[i] - sum_di[hi[i]];
}
sort(val+,val+m+);
sum[] = ;
for (int i = ; i<=m; i++) {
sum[i] = sum[i-] + val[i];
}
/* for (int i =1; i<=m; i++) {
cout << val[i] << " ";
}cout<<endl;
*/
}
LL dp[][N];
void solve(){
init_val();
for (int i = ; i <= m; i++) {
dp[][i] = val[i]*i - sum[i];
}
LL ret = dp[][m];
for (int j = ; j<=p; j++) {
init();
for (int i = ; i <= m; i++) {
pop(-val[i]);
dp[j][i] = -val[i]*q[head].x + q[head].y - sum[i] + val[i]*i;
push(Point(i,dp[j-][i] + sum[i])); }
if (dp[j][m] < ret) ret = dp[j][m];
}
printf("%I64d\n",ret);
}
int main(){
freopen("in.txt","r",stdin);
while (~scanf("%d%d%d",&n,&m,&p)){
for (int i = ; i <= n ;i++) scanf("%I64d",di+i);
sum_di[] = sum_di[] = ;
for (int i = ; i <= n; i++) sum_di[i] = sum_di[i-] + di[i];
for (int i= ; i <= m; i++) scanf("%I64d%I64d",hi+i,ti+i);
solve();
}
return ;
}
hdu 3669
/*
题意：n个A矩形，至多在墙上挖M个B矩形，每个B矩形的花费是矩形的面积，且每个B矩形不能重叠，
使所有A矩形都能通过，（A矩形不能旋转），问最小的花费； 按照wi从大到小，如果wi相等，则按hi从大到小排，这样对于wi相同的矩形，只要hi最高的能通过，其他
的肯定能通过，这样可以预处理出必要的矩形； 这样问题就变成，给你wi递减，hi递增的矩形序列，至多分成M段，没段的花费为
w[i,j] = mat[i].wi*mat[j].hi; 设DP[j][i]表示将前i个矩形划分成j段的最小花费；
DP[j][i] = DP[j-1][k] + w[k,i]; 很标准的斜率DP； 注意： 常数很大，写在结构体里就T了，还有就是能不用LL的就不要用LL，
用LL的常数也很大，
还有就是一个可以”优化“的，就是if dp[j][n] > ret then break; 标记为“>.<”的那行；
但是不知道是不是对的
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
const int N=+;
typedef long long LL;
struct Point{
int x;
LL y;
Point (int a=,LL b=):x(a),y(b){}
Point operator - (const Point &p) const{
return Point(x-p.x,y-p.y);
}
};
typedef Point Vector;
inline LL Cross(const Vector &u,const Vector &v){
return (LL)u.x*v.y - (LL)u.y*v.x;
}
struct rec{
int w,h;
bool operator < (const rec &p)const{
return w>p.w || (w==p.w && h>p.h);
}
}mat[N];
int n,M;
Point q[N];
int head,tail;
/*
struct dequeue{
Point q[N];
int head,tail;
void init(){
head = 1; tail = 0;
}
void push(const Point &u){
while (head < tail && Cross(q[tail]-q[tail-1],u-q[tail-1]) >= 0 ) tail--;
q[++tail] = u;
}
Point pop(const LL &k){
while (head < tail && k*q[head].x + q[head].y >= k*q[head+1].x + q[head+1].y ) head++;
return q[head];
}
}H;
*/
LL dp[][N];
void solve(){ sort(mat+,mat+n+);
int tn=;
for (int i=;i<=n;i++){
if (mat[tn].w!=mat[i].w && mat[tn].h < mat[i].h) mat[++tn] = mat[i];
}
n = tn; LL ret = -;
int pos=;
dp[pos][] = ;
for (int i=;i<=n;i++){
dp[pos][i]=(LL)mat[].w*mat[i].h;
}
ret = dp[pos][n];
for (int j=;j<=M;j++){
head = ; tail = ;
for (int i=;i<=n;i++){
Point u=Point(mat[i].w,dp[pos][i-]);
while (head < tail && Cross(q[tail]-q[tail-],u-q[tail-]) >= ) tail--;
q[++tail] = u;
while (head < tail && (LL)q[head].x*mat[i].h + q[head].y >= (LL)q[head+].x*mat[i].h + q[head+].y )
head++; dp[pos^][i] = (LL)q[head].x*mat[i].h + q[head].y;
} pos ^= ; dp[pos][] = ;
if (dp[pos][n] < ret) ret = dp[pos][n];
//else break； >.<
}
printf("%I64d\n",ret);
}
int main(){
//freopen("in.txt","r",stdin);
while (~scanf("%d%d",&n,&M)){
for (int i=;i<=n;i++){
scanf("%d%d",&mat[i].w,&mat[i].h);
}
solve();
}
return ;
}
hdu 3725
/*
题意：happy Farm，偷菜，且只能按照价值从大到小开始偷（一般斜率DP都是这样，有一定的顺序，然后就是分段了）
每个蔬菜有两个值ai,di，可以刷新M次，每次刷新后DOG的anger值变成0; 抽象一下：给你一个序列，至多分成M段，每段的花费是w[i,j];
在花费小于ti的情况下，使每段sum_di的最大值最小； w[i+1,j] = a[i+1]*1 + a[i+2]*2 + ... + a[j]*(j-i+1); 最大值最小，很容易让人想到二分最大值m，然后判断是否满足； 现在问题变成：每段sum_di的值不超过m,问是否存在方案使得花费小于ti； Ti[i] = a[1]*1 + a[2]*2 + ... + a[i]*i;
sum[i] = a[1] + a[2] + ... + a[i];
w[i+1,j] = Ti[j] - Ti[i] - sum[i]*(j-i); dp[j][i]表前i个蔬菜，分成j段，每段sum_di满足要求下的最小花费；
dp[j[i] = dp[j-1][k] + w[k,i]; 显然也是一个斜率DP模型； 因为每段加了一个sum_di不能超过m的要求，所以在POP时还要POP掉不能满足条件的点
这就有可能H.q[]里一个点也没有，anger[i]本身大于m,所以我们在操作时要判断一下，
同样在PUSH时也是，不需要把那些不满足的点push进去； 初始化，和队列的边界问题我想是写斜率DP的唯一要注意一下的地方； */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
using namespace std;
const int N=+;
typedef long long LL;
struct Point{
LL x,y;
Point (LL a=,LL b=):x(a),y(b){}
Point operator - (const Point &p)const{
return Point(x - p.x, y - p.y);
}
};
LL sum[N],Ti[N],ti;
int n,M,r,anger[N];
typedef Point Vector;
LL Cross(const Vector &u,const Vector &v){
return u.x*v.y - u.y*v.x;
}
struct dequeue{
Point q[N];
int head,tail;
void init(){
head = ; tail = ;
}
void push(const Point &u){
while (head < tail && Cross(q[tail] - q[tail-],u - q[tail-]) <= )
tail--;
q[++tail] = u;
}
void pop(int k,int i,int w){
while (head <= tail && anger[i] - anger[q[head].x] > w) head++;
while (head < tail && -k*q[head].x + q[head].y >= -k*q[head+].x + q[head+].y) head++; }
}H; struct vegetable{
int vi,ai;
LL di;
vegetable(int v=,int a=,LL d=):vi(v),ai(a),di(d){}
bool operator < (const vegetable &p)const{
return vi>p.vi;
}
void input(){
scanf("%d%d%I64d",&vi,&ai,&di);
}
void output(){
cout<< vi <<" "<< ai <<" "<< di << endl;
} }vg[N]; void init(){
sort(vg+,vg+n+);
anger[] = sum[] = Ti[] = ;
for (int i=;i<=n;i++) {
sum[i]=sum[i-]+vg[i].di;
Ti[i]=Ti[i-]+i*vg[i].di;
anger[i] = anger[i-] + vg[i].ai;
}
/*
for (int i=0;i<=n;i++) cout<<sum[i]<<" ";cout<<endl;
for (int i=0;i<=n;i++) cout<<Ti[i]<<" ";cout<<endl;
for (int i=0;i<=n;i++) cout<<anger[i]<<" ";cout<<endl;
*/
}
LL dp[][N];
int check(int m){
for (int i = ; i <= M; i++){
for (int j = ; j <= n; j++) dp[i][j] = -;
}
for (int i=;i<=n;i++){
if (anger[i] <= m) dp[][i]=Ti[i];
else break;
}
for (int j=;j<=M;j++){ H.init();
H.push(Point(,(j-)*r)); for (int i=;i<=n;i++){
H.pop(sum[i],i,m);
if (H.head<=H.tail)
dp[j][i] = -sum[i]*H.q[H.head].x + H.q[H.head].y + Ti[i] + r;
//cout<< t.x << " " << t.y << " *** " <<dp[j][i]<< endl;
if (dp[j-][i] != -) H.push(Point(i,sum[i]*i + dp[j-][i] - Ti[i])); }
}
LL ret = dp[][n];
for (int i=; i<=M;i++){
if(dp[i][n] < ret || ret == -) ret = dp[i][n];
}
if (ret > ti || ret == -) return ;
return ;
}
void solve(int l,int r){
init();
int ret=-;
while (r>=l){
int m=(l+r)>>;
if (check(m)){
ret=m; r=m-;
}else l=m+;
}
if (ret == -) printf("I have no idea\n");
else printf("%d\n",ret);
}
int main(){ freopen("in.txt","r",stdin);
int T; scanf("%d",&T);
while (T--){
scanf("%d%d%d%I64d",&n,&M,&r,&ti);
int allai = ;
for (int i=;i<=n;i++){
vg[i].input();
allai += vg[i].ai;
}
solve(,allai);
}
return ;
}