@ivorysi 2018-01-02T09:02:27.000000Z 字数 24415 阅读 714

动态规划学习笔记

笔记

矩阵乘法

POJ 3070 Fibonacci

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

题解

矩乘递推斐波那契第n项取模10000

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
struct matrix {
    int f[3][3];
    matrix() {
        memset(f,0,sizeof(f));
    }
    friend matrix operator *(const matrix &a,const matrix &b) {
        matrix c;
        siji(i,1,2) {
            siji(j,1,2) {
                siji(k,1,2) {
                    c.f[i][j]+=a.f[i][k]*b.f[k][j]%10000;
                    c.f[i][j]%=10000;
                }
            }
        }
        return c;
    }
}a,ans;
void fpow(int c) {
    matrix t=a;
    while(c) {
        if(c&1) ans=ans*t;
        t=t*t;
        c>>=1;
    }
}
int n;
void solve() {
    if(n==0) {puts("0");return;}
    if(n==1 || n==2) {puts("1");return;}
    memset(ans.f,0,sizeof(ans.f));
    ans.f[1][1]=ans.f[2][2]=1;
    fpow(n-2);
    printf("%d\n",(ans.f[1][1]+ans.f[1][2])%10000);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    a.f[1][1]=a.f[1][2]=a.f[2][1]=1;
    while(scanf("%d",&n)!=EOF) {
        if(n==-1) break;
        solve();
    }
    return 0;
}

BZOJ 1009 1009: [HNOI2008]GT考试

Description

阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为
0

Input

第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

题解

这道题 $dp[i][k]$ 表示到第i位匹配到第k个字符有多少种情况，要求k 转移方程可以考虑在i后面加一位匹配，看最多能匹配到哪
方程就是 $dp[i][k]=\sum_{j=0}^{m-1}dp[i-1][j]*a[i][j]$
$a[i][j]$ 表示加一位后从i匹配到j有几种情况
然后进行矩乘优化

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
using namespace std;
typedef long long ll;
int n,m,mod;
char s[40];
struct matrix {
    int f[25][25];
    matrix() {
        memset(f,0,sizeof(f));
    }
    friend matrix operator *(const matrix &a,const matrix &b) {
        matrix c;
        xiaosiji(i,0,m) {
            xiaosiji(j,0,m) {
                xiaosiji(k,0,m) {
                    c.f[i][j]+=a.f[i][k]*b.f[k][j]%mod;
                    c.f[i][j]%=mod;
                }
            }
        }
        return c;
    }
}a,ans;
void fpow(int c) {
    matrix t=a;
    while(c) {
        if(c&1) ans=ans*t;
        t=t*t;
        c>>=1;
    }
}
int nxt[25];
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",s+1);
    siji(i,2,m) {
        int p=nxt[i-1];
        while(p && s[p+1]!=s[i]) p=nxt[p];
        if(s[p+1]==s[i]) nxt[i]=p+1;
        else nxt[i]=0;
    }
    xiaosiji(i,0,m) {
        siji(j,0,9) {
            if(s[i+1]=='0'+j) {
                if(i+1==m) continue;
                ++a.f[i+1][i];continue;
            } 
            int k=nxt[i];
            while(k && s[k+1]!=j+'0') k=nxt[k];
            if(s[k+1]=='0'+j) ++a.f[k+1][i];
            else ++a.f[0][i];
        }
    }
    xiaosiji(i,0,m) ans.f[i][i]=1;
    fpow(n);
    int res=0;
    xiaosiji(i,0,m) {
        res+=ans.f[i][0];
        res%=mod;
    }
    printf("%d\n",res);
    return 0;
}

BZOJ 3329: Xorequ

Description

Input

第一行一个正整数，表示数据组数据，接下来T行
每行一个正整数N

Output

2*T行
第2*i-1行表示第i个数据中问题一的解，
第2*i行表示第i个数据中问题二的解，

Sample Input

1
1

Sample Output

1
2

HINT

x=1与x=2都是原方程的根，注意第一个问题的解
不要mod 10^9+7
1<=N<=10^18
1<=T<=1000

题解

我们要注意到这样一个结论
a^b=c可以得到a^c=b
证明可以是a^b^b^c=c^b^c
a^c=b
然后我们发现x^2x=3x
2x是把x整体左移，那么我们可以得知这样的x是没有两个连续的1，才能让异或变成加法
这样的数可以用数位dp解决
递推方程是
dp[i][0]=dp[i-1][0]+dp[i-1][1]
dp[i][1]=dp[i-1][0]
dp[i][1/0]表示长度为i的二进制数最高位是1或者是0
然后这个递推方程的边界是dp[1][0]=dp[1][1]=1
写成递推矩阵的话和斐波那契的矩阵其实是一样的
第二问可以这么考虑 $2^n$ 的答案，是dp[n+1][0]，去掉0的情况再加上 $2^n$ 的情况，答案就是dp[n+1][0]用矩阵递推出来即可

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
struct matrix {
    ll f[3][3];
    matrix() {
        memset(f,0,sizeof(f));
    }
    friend matrix operator * (const matrix &a,const matrix &b) {
        matrix c;
        siji(i,1,2) {
            siji(j,1,2) {
                siji(k,1,2) {
                    c.f[i][j]+=a.f[i][k]*b.f[k][j]%mod;
                    c.f[i][j]%=mod;
                }
            }
        }
        return c;
    }
}a,tar;
ll n;
ll dp[70][2];
void fpow(ll c) {
    matrix t=a;
    while(c) {
        if(c&1) tar=tar*t;
        t=t*t;
        c>>=1;
    }
}
void solve() {
    scanf("%lld",&n);
    ll ans=0;
    bool content=false;
    gongzi(i,61,0) {
        ll k=(ll)1<<i;
        if(n&k) {
            if(!content) ans+=dp[i+1][0];
            ll t=(ll)1<<(i+1);
            if(n&t) content=true;
        }
    }
    if((n^(2*n))==(3*n)) ++ans;
    --ans;
    printf("%lld\n",ans);
    memset(tar.f,0,sizeof(tar.f));
    tar.f[1][1]=tar.f[2][2]=1;
    fpow(n);
    printf("%lld\n",(tar.f[1][1]+tar.f[1][2])%mod);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    int T;
    scanf("%d",&T);
    a.f[1][1]=a.f[1][2]=a.f[2][1]=1;
    dp[1][0]=dp[1][1]=1;
    siji(i,2,65) {
        dp[i][1]=dp[i-1][0];
        dp[i][0]=dp[i-1][1]+dp[i-1][0];
    }
    while(T--) {
        solve();
    }
    return 0;
}

BZOJ 1297: [SCOI2009]迷路

Description

windy在有向图中迷路了。该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

Input

第一行包含两个整数，N T。接下来有 N 行，每行一个长度为 N 的字符串。第i行第j列为'0'表示从节点i到节点j没有边。为'1'到'9'表示从节点i到节点j需要耗费的时间。

Output

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

Sample Input

【输入样例一】

2 2
11
00

【输入样例二】

5 30
12045
07105
47805
12024
12345

Sample Output

【输出样例一】
1
【样例解释一】
0->0->1
【输出样例二】
852

HINT

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。 100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

题解

我的做法比较愚蠢，因为可以把一个点拆成很多10个点，这样就可以用邻接矩阵递推
这种做法上一个时间向下一个时间连一条边，然后条边按照边权从i的k时间点向j连一条边
还有一种
dp[u][t]表示到点u时间为t的方案数
矩阵是显然的，100个点递推即可（然而把9写成8的我真的是要蠢死了……）
初始化的时候还要把前9个时间递推一下
然而这道题说是T恰好到n-1，它还有可能中途到了n-1然后在晃悠几圈，很迷

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
int n;
struct matrix {
    int f[105][105];
    matrix() {
        memset(f,0,sizeof(f));
    }
    friend matrix operator * (const matrix &a,const matrix &b) {
        matrix c;
        siji(i,1,100) {
            siji(j,1,100) {
                siji(k,1,100) {
                    c.f[i][j]+=a.f[i][k]*b.f[k][j]%2009;
                    c.f[i][j]%=2009;
                }
            }
        }
        return c;
    }
}a,tar;
char s[15][15];
int T,dp[15][15],l[105],tot;
void fpow(int c) {
    matrix t=a;
    while(c) {
        if(c&1) tar=tar*t;
        t=t*t;
        c>>=1;
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&T);
    siji(i,1,n) scanf("%s",s[i]+1);
    siji(i,1,n) {
        siji(j,1,n) {
            if(s[i][j]-'0'!=0) {
                int k=s[i][j]-'0';
                a.f[j*10][i*10-k+1]=1;
            }
        }
        siji(j,1,9) a.f[(i-1)*10+j][(i-1)*10+j+1]=1;//虽然是0-8但是9个点orz
    }
    dp[1][0]=1;
    siji(h,1,9) {
        siji(i,1,n) {
            siji(j,1,n) {
                int k=s[i][j]-'0';
                if(k==0) continue;
                if(h<k) continue;
                dp[j][h]=(dp[j][h]+dp[i][h-k])%2009;
            }
        }
    }
    if(T<=9) {printf("%d\n",dp[n][T]);return 0;}
    siji(i,1,n) {
        siji(j,0,9) {
            l[++tot]=dp[i][j];
        }
    }
    siji(i,1,n*10)tar.f[i][i]=1;
    fpow(T-10);
    int ans=0;
    siji(i,1,n) {
        int k=s[i][n]-'0';
        if(k==0) continue;
        int t=i*10-k+1;
        siji(j,1,tot) ans+=l[j]*tar.f[t][j]%2009,ans%=2009;
    }
    printf("%d\n",ans);
    return 0;
}

模型1

我们对于一个这样的式子
$f(x)=min_{i=0}^{x}\{ f(i)+w[i,x]\}$
是有决策单调性的
什么是决策单调性呢，加入我们用x更新的i，y更新的j,在i < j的情况下 x <= y
例如我们一开始只有f[0]这个决策
我们对于决策的更新就是

1111111111111111111111111

然后又有了一个新决策，决策的更新方式是这样的

1111111111222222222222222

之后再来一个决策

1111111111222222223333333

或者是

1111113333333333333333333

而不可能是

1111111111333332222222222

所以我们用一个队列，每次拿新决策和队尾的老决策进行比较，如果在老决策的起点处新决策最优，就全部舍弃老决策
否则老决策中肯定有一个转折点，我们可以二分找到这个转折点

BZOJ 1597: [Usaco2008 Mar]土地购买

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

Input

第1行: 一个数: N

第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽

Output

第一行: 最小的可行费用.

Sample Input

4
100 1
15 15
20 5
1 100

输入解释:

共有4块土地.

Sample Output

500

HINT

FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 plot. 每组的价格分别为100,100,300, 总共500.

题解

这道题可能看起来没有决策单调性，但是我们把所有点按照长度排序后，我们后面的决策只和宽度有关
$f(x)=min_{i=0}^{x} \{ f(i)+max_{j=i+1}^{x} width×length[i+1]\}$
这似乎不是那个模型，可是把这些点画在一个二维坐标里就会发现
有的土地长宽都被另一块土地覆盖了，则可以舍弃不考虑
这些点扫一遍就可以求出来，然后对于剩下的点，我们就有
$f(x)=min_{i=0}^{x} \{ f(i)+length[i+1]*width[x]\}$
这就满足那个式子了，可以直接应用上述的决策单调性

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 50005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
struct node {
    ll len,wid;
    bool operator < (const node &b) const{
    return len>b.len || (len==b.len && wid>b.wid);
    }
}tmp[MAXN],area[MAXN];
int n,tot,que[MAXN][3],t,h;
ll f[MAXN];
ll calc(int l,int z) {
    return f[l]+area[l+1].len*area[z].wid;
}
void solve() {
    n=read();
    siji(i,1,n) {
    tmp[i].len=read();
    tmp[i].wid=read();
    }
    sort(tmp+1,tmp+n+1);
    ll maxwid=0;
    siji(i,1,n) {
    if(tmp[i].wid>maxwid) {
        area[++tot]=tmp[i];
    }
    maxwid=max(tmp[i].wid,maxwid);
    }
    h=t=1;
    que[1][0]=0,que[1][1]=0,que[1][2]=tot;
    siji(i,1,tot) {
    if(que[h][1]<que[h][2]) ++que[h][1];
    else ++h;
    f[i]=calc(que[h][0],i);
    if(calc(i,tot)>=calc(que[t][0],tot)) continue;
    while(h<=t && calc(que[t][0],que[t][1])>=calc(i,que[t][1])) --t;
    if(h>t) {
        que[++t][0]=i,que[t][1]=i,que[t][2]=tot;
    }
    else {
        int l=que[t][1],r=que[t][2];
        while(l<r) {
        int m=(l+r+1)>>1;
        if(calc(que[t][0],m)<calc(i,m)) {
            l=m;
        }
        else {
            r=m-1;
        }
        }
        que[t][2]=l;
        que[++t][0]=i,que[t][1]=l+1,que[t][2]=tot;
    }
    }
    printf("%lld\n",f[tot]);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
}

BZOJ 1096: [ZJOI2007]仓库建设

Description

L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内
陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象
部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于
地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库
的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设
置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，
假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到
以下数据：1：工厂i距离工厂1的距离Xi（其中X1=0）;2：工厂i目前已有成品数量Pi;:3：在工厂i建立仓库的费用
Ci;请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。

Input

第一行包含一个整数N，表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。

Output

仅包含一个整数，为可以找到最优方案的费用。

Sample Input

3
0 5 10
5 3 100
9 6 10

Sample Output

32

HINT

在工厂1和工厂3建立仓库，建立费用为10+10=20，运输费用为(9-5)*3 = 12，总费用32。如果仅在工厂3建立仓库，建立费用为10，运输费用为(9-0)*5+(9-5)*3=57，总费用67，不如前者优。

【数据规模】

对于100%的数据， N ≤1000000。所有的Xi, Pi, Ci均在32位带符号整数以内，保证中间计算结果不超过64位带符号整数。

题解

这道题显然是有决策单调性的，因为我们dp[k]表示位置为k的地方建仓库使得1-k能够全部有仓库存放的总花费
我们从某个i转移，显然i越大，转移到k的花费就越小，然后考虑决策单调性，打个表然后看看是不是……然后愉快的套算法
$dp[k]=max_{i=0}^{k-1}\{dp[i]+p[k]+\sum_{z=i+1}^{k-1}(dis[k]-dis[z])*num[z]\}$
然后拆式子
$dp[k]=max_{i=0}^{k-1}\{dp[i]+p[k]+\sum_{z=i+1}^{k-1}dis[k]*num[z]-\sum_{z=i+1}^{k-1}dis[z]*num[z]\}$
$dp[k]=max_{i=0}^{k-1}\{dp[i]+p[k]+dis[k]\sum_{z=i+1}^{k-1}num[z]-\sum_{z=i+1}^{k-1}dis[z]*num[z]\}$
然后那两个式子就可以通过前缀和来维护了，这道题就做完了

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1000005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int n;
ll dis[MAXN],num[MAXN],gar[MAXN];
ll sum1[MAXN],sum2[MAXN],dp[MAXN];//sum1 num sum2 dis*num
int que[MAXN][3],qh,qt;
ll calc(int l,int z) {
    return dp[l]+dis[z]*(sum1[z-1]-sum1[l])-(sum2[z-1]-sum2[l])+gar[z];
} 
void solve() {
    n=read();
    siji(i,1,n) {
    dis[i]=read();
    num[i]=read();
    gar[i]=read();
    }
    siji(i,1,n) {
    sum1[i]=num[i]+sum1[i-1];
    sum2[i]=dis[i]*num[i]+sum2[i-1];
    }
    qh=qt=1;
    que[1][0]=0;que[1][1]=0;que[1][2]=n;
    siji(i,1,n) {
    if(que[qh][1]<que[qh][2]) ++que[qh][1];
    else ++qh;
    dp[i]=calc(que[qh][0],i);
    if(calc(que[qt][0],n)<=calc(i,n)) continue;
    while(qh<=qt && calc(que[qt][0],que[qt][1])>=calc(i,que[qt][1])) --qt;
    if(qh>qt) {
        que[++qt][0]=i;que[qt][1]=i;que[qt][2]=n;
    }
    else {
        int l=que[qt][1],r=que[qt][2];
        while(l<r) {
        int m=(l+r+1)>>1;
        if(calc(que[qt][0],m)<=calc(i,m)) {
            l=m;//这里都打成l=i了
        }
        else {
            r=m-1;
        }
        }
        que[qt][2]=l;
        que[++qt][0]=i;que[qt][1]=l+1;que[qt][2]=n;
    }
    }
    printf("%lld\n",dp[n]);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
}

模型2

还有这样一个式子
$f(x)=min_{k=b[x]}^{x-1}\{g[k]\}+w[x]$ 其中b[x]随x不降
这样的话我们可以注意到，如果 $g(k)<=g(j)$ , $j<k$ 那么j必然无用，可以舍去
这让我们考虑到单调队列，我们可以用单调队列来维护这个东西，让队首控制在合法的范围内，然后保持整个队列单调递增，每次用队首来更新即可

经典例题

多重背包问题

二进制优化可以使得多重背包的复杂度降到log级别，但是还有更好的O(NP)做法，N是物品个数，P是背包体积

现在我们有N种物品
每种物品有一个价值val[i],一个体积weight[i],还有一个数目num[i]
现在给你一个体积为P的背包，求最大价值

题解

对于一个体积为i的背包f[i],当前枚举到背包的种类是x，我们可以从 $i-weight[x]$ , $i-2*weight[x]$ .... $i-num[x]*weight[x]$ 转移过来
然后我们可以写出方程
$f[i]=max_{k=0}^{num[x]}\{f[i-k*weight[x]]+k*val[x]\}$
然而这个方程……在i移动的时候(i-k×weight[x])都会变化，不满足模型啊……怎么办呢……
我们发现，对于一个固定的物品，每段体积的转移都是%weight[x]相等的，所以我们可以选择从weight[x]的剩余系开始枚举，逐个加倍
然后再观察这个式子，考虑变形
$f[v+t*weight[x]]=max_{k=0}^{num[x]}\{f[v+(t-k)*weight[x]]+k*val[x]\}$
$f[v+t*weight[x]]=max_{k=0}^{num[x]}\{f[v+(t-k)*weight[x]]-(t-k)*val[x]\}+t*val[x]$
设t-k=z
$f[v+t*weight[x]]=max_{z=t-num[x]}^{t}\{f[v+z*weight[x]]-z*val[x]\}+t*val[x]$
这样我们发现，和k并没有什么关系，我们把队首的范围控制一下，就好了
这个问题就被优化成O(NP)了

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <set>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
//#define ivorysi
#define MAXN 105
#define ha 9779797
using namespace std;
typedef long long ll;
ll dp[50005];
int n,w;
int v[105],p[105],c[105];
int q[50005],head,tail,poi;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&w);
    siji(i,1,n) {
        scanf("%d%d%d",&v[i],&p[i],&c[i]);
    }
    siji(i,1,n) {
        xiaosiji(j,0,v[i]) {
            int k=(w-j)/v[i];
            head=tail=1;
            poi=k-1;
            gongzi(l,k,1) {
                for(;poi>=(l-c[i]) && poi>=0;--poi) {
                    while(tail>1 && 
                        dp[q[tail-1]*v[i]+j]-q[tail-1]*p[i]<dp[poi*v[i]+j]-poi*p[i]) --tail;
                    q[tail++]=poi;
                }
                if(q[head]==l) ++head;
                //if(head>=tail) continue;
                dp[l*v[i]+j]=max(dp[l*v[i]+j],dp[q[head]*v[i]+j]-q[head]*p[i]+l*p[i]);
            }
        }
    }
    printf("%lld\n",dp[w]);
}

BZOJ 1499: [NOI2005]瑰丽华尔兹

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼•布德曼•T.D.•柠檬•1900，朋友们都叫他1900。 1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上，很不幸他刚出生就被抛弃了，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。可能是天使的点化，1900拥有不可思议的钢琴天赋：从未有人教，从没看过乐谱，但他却能凭着自己的感觉弹出最沁人心脾的旋律。当1900的音乐获得邮轮上所有人的欢迎时，他才8岁，而此时的他已经乘着海轮往返欧美大陆50余次了。虽说是钢琴奇才，但1900还是个孩子，他有着和一般男孩一样的好奇和调皮，只不过更多一层浪漫的色彩罢了：这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手马克斯•托尼晕船了，1900招呼托尼和他一起坐上舞厅里的钢琴，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾斜滑动起来。准确的说，我们的主角1900、钢琴、邮轮随着1900的旋律一起跳起了华尔兹，随着“嘣嚓嚓”的节奏，托尼的晕船症也奇迹般的消失了。后来托尼在回忆录上写道：大海摇晃着我们使我们转来转去快速的掠过灯和家具我意识到我们正在和大海一起跳舞真是完美而疯狂的舞者晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢？也许，我们忘记了一个人，那就是艾米丽，她可没闲着：她必须在适当的时候施展魔法帮助1900，不让钢琴碰上舞厅里的家具。不妨认为舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行路程尽量长，这样1900会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。

Input

输入文件的第一行包含5个数N, M, x, y和K。N和M描述舞厅的大小，x和y为钢琴的初始位置（x行y列）；我们对船体倾斜情况是按时间的区间来描述的，且从1开始计量时间，比如“在[1, 3]时间里向东倾斜，[4, 5]时间里向北倾斜”，因此这里的K表示区间的数目。以下N行，每行M个字符，描述舞厅里的家具。第i行第j列的字符若为‘ . ’，则表示该位置是空地；若为‘ x ’，则表示有家具。以下K行，顺序描述K个时间区间，格式为：si ti di。表示在时间区间[si, ti]内，船体都是向di方向倾斜的。di为1, 2, 3, 4中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即 s1 = 1 si = ti-1 + 1 (1 < i ≤ K) tK = T

Output

输出文件仅有1行，包含一个整数，表示钢琴滑行的最长距离(即格子数)。

Sample Input

4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

Sample Output

6

题解

复杂度是 $O(nmk)$
单调队列优化一发……对于四个方向采取不同的维护，再枚举每个点进行更新是 $O(1)$ 的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1000005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int n,m,x,y,k;
int s,t,d;
char map[305][305];
int dp[2][305][305],now,que[305],hd,tl;
void calc1() {
    int delta=t-s+1;
    siji(j,1,m) {
        hd=1,tl=0;
        que[1]=0;
        gongzi(i,n,1) {
            if(map[i][j]=='x') {hd=1,tl=0;que[1]=0;continue;}
            while(hd<=tl && que[hd]>i+delta) ++hd;
            if(hd<=tl && dp[now][que[hd]][j]!=0) {
                dp[now^1][i][j]=dp[now][que[hd]][j]+que[hd]-i;
            }
            dp[now^1][i][j]=max(dp[now][i][j],dp[now^1][i][j]);
            if(dp[now][i][j]==0) continue;
            while(hd<=tl && dp[now][que[tl]][j]+que[tl]<dp[now][i][j]+i) --tl;
            que[++tl]=i;
        }
    }
}
void calc2() {
    int delta=t-s+1;
    siji(j,1,m) {
        hd=1,tl=0;
        que[1]=0;
        siji(i,1,n) {
            if(map[i][j]=='x') {hd=1,tl=0;que[1]=0;continue;}
            while(hd<=tl && que[hd]<i-delta) ++hd;
            if(hd<=tl && dp[now][que[hd]][j]!=0) {
                dp[now^1][i][j]=dp[now][que[hd]][j]+i-que[hd];
            }
            dp[now^1][i][j]=max(dp[now][i][j],dp[now^1][i][j]);
            if(dp[now][i][j]==0) continue;
            while(hd<=tl && dp[now][que[tl]][j]-que[tl]<dp[now][i][j]-i) --tl;
            que[++tl]=i;
        }
    }
}
void calc3() {
    int delta=t-s+1;
    siji(i,1,n) {
        hd=1,tl=0;
        que[1]=0;
        gongzi(j,m,1) {
            if(map[i][j]=='x') {hd=1,tl=0;que[1]=0;continue;}
            while(hd<=tl && que[hd]>j+delta) ++hd;
            if(hd<=tl && dp[now][i][que[hd]]!=0) {
                dp[now^1][i][j]=dp[now][i][que[hd]]+que[hd]-j;
            }
            dp[now^1][i][j]=max(dp[now][i][j],dp[now^1][i][j]);
            if(dp[now][i][j]==0) continue;
            while(hd<=tl && dp[now][i][que[tl]]+que[tl]<dp[now][i][j]+j)--tl;
            que[++tl]=j;
        }
    }
}
void calc4() {
    int delta=t-s+1;
    siji(i,1,n) {
        hd=1;tl=0;
        que[1]=0;
        siji(j,1,m) {
            if(map[i][j]=='x') {hd=1,tl=0;que[1]=0;continue;}
            while(hd<=tl && que[hd]<j-delta) ++hd;
            if(hd<=tl && dp[now][i][que[hd]]!=0) {
                dp[now^1][i][j]=dp[now][i][que[hd]]+j-que[hd];
            }
            dp[now^1][i][j]=max(dp[now][i][j],dp[now^1][i][j]);
            if(dp[now][i][j]==0) continue;
            while(hd<=tl && dp[now][i][que[tl]]-que[tl]<dp[now][i][j]-j)--tl;
            que[++tl]=j;
        }
    }
}
void solve() {
    n=read();m=read();x=read();y=read();k=read();
    dp[now][x][y]=1;
    siji(i,1,n) {
        scanf("%s",map[i]+1);
    }
    if(map[x][y]=='x') dp[now][x][y]=0;
    siji(i,1,k) {
        s=read();t=read();d=read();
        if(d==1) calc1();
        else if(d==2) calc2();
        else if(d==3) calc3();
        else calc4();
        now^=1;
    }
    int ans=0;
    siji(i,1,n) {
        siji(j,1,m) {
            ans=max(ans,dp[now][i][j]);
        }
    }
    --ans;
    if(ans<0) ans=0;
    printf("%d",ans);
}
int main() {
    solve();
}

模型3

$f[n]=max_{i=0}^{n-1}\{a[n]*x[i]+b[n]*y[i]\}$
拿 $x[i]$ 作为横轴， $y[i]$ 作为纵轴
$min P=ax+by$
$y=-\frac{a}{b}x+\frac{1}{b}P$
我们发现，最优决策一定在平面内的一个凸包上，然后相当于一个斜率一定的直线自负无穷向上平移，碰到的一个数据点即为答案
然后如果直线的斜率和二元组 $(x,y)$ 的x坐标同时满足单调性，那么我们可以维护一个凸壳，然后用一个单调队列维护凸壳上的点，我们从队列前往后找一个最优的的点，因为前面的点斜率一定不优，而斜率单调变化，前面舍弃的点一定没有用了，然后我们用叉乘维护这个凸壳下凸就可以了
其实在代码实现里，这个直线是不用存在的，因为从前往后去计算决策的那个式子，找一个最优解，就相当于比较斜率了

BZOJ 1010: [HNOI2008]玩具装箱toy

Description

P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压
缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过
压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容
器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一
个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，
如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容
器，甚至超过L。但他希望费用最小.

Input

第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

题解

sum表示前缀和
$f[x]=min\{f[i]+(sum[x]-sum[i]+x-i-1-L)^2\}$
然后分个类
$f[x]=min\{f[i]+((sum[x]+x-L-1)-(sum[i]+i))^2\}$
设 $a[x]$ 是 $sum[x]+x-L-1$
$b[i]$ 是 $sum[i]+i$
$f[x]=min\{f[i]+b[i]^2-2\cdot a[x]\cdot b[i]\}+a[x]^2$
把 $f[i]+b[i]^2$ 作为y轴
把 $b[i]$ 作为x轴
斜率单调增，x轴左边单调增，维护一个下凸壳，取最小值

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 50005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int n;
ll L,c[MAXN];
ll a[MAXN],b[MAXN],sum[MAXN],X[MAXN],Y[MAXN],f[MAXN];
int que[MAXN],qh,qt;
ll calc(int l,int z) {
    return f[l]-2*a[z]*b[l]+b[l]*b[l];
}
bool slope(int l,int z,int s) {
    return (X[l]-X[s])*(Y[z]-Y[s])-(X[z]-X[s])*(Y[l]-Y[s])>=0;
}
void solve() {
    n=read();
    L=read();
    siji(i,1,n) {
    c[i]=read();
    sum[i]=sum[i-1]+c[i];
    }
    siji(i,1,n) {
    b[i]=sum[i]+i;
    a[i]=b[i]-L-1;
    }
    qh=qt=1;que[1]=0;
    siji(i,1,n) {
    while(qh<qt && calc(que[qh],i)>=calc(que[qh+1],i)) ++qh;
    f[i]=calc(que[qh],i)+a[i]*a[i];
    X[i]=b[i];Y[i]=f[i]+b[i]*b[i];
    while(qh<qt && slope(que[qt],que[qt-1],i)) --qt;
    que[++qt]=i;
    }
    printf("%lld\n",f[n]);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    solve();
}

BZOJ 1911: [Apio2010]特别行动队

给出一个数N表示一共有N个士兵，每个士兵有一个战斗力
然后将士兵分成任意多个连续区间，每个区间的值是 $ax^2+bx+c$ 然后求这些值的和最大是多少

输入

第一行给出一个N
第二行给出a,b,c
然后给出N个数，是每个士兵的战斗力

输出

战斗力最大的总和

题解

推式子
$f[k]=max_{i=0}^{k-1}\{f[i]+a(sum[k]-sum[i])^2+b(sum[k]-sum[i])+c\}$
$f[k]=max_{i=0}^{k-1}\{f[i]+a*sum[i]^2-b*sum[i]-2*a*sum[x]*sum[i]\}+a*sum[k]^2+b*sum[k]+c$
然后拿 $f[i]+a*sum[i]^2-b*sum[i]$ 作为y轴， $sum[i]$ 作为x轴
横坐标单调增，斜率单调减
由于要取最大值，所以我们需要维护一个上凸的凸包

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <set>
#include <queue>
#include <map>
#define siji(i,x,y) for(int i=(x);i<=(y);i++)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define pii pair<int,int>
#define fi first
#define se second
//#define ivorysi
#define MAXN 1000005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')neg=-1;
        c=getchar();
    }
    while(c>='0'&&c<= '9') {
        res=res*10+c-'0';
        c=getchar();
    }
    return res*neg;
}
void out(ll x) {
    if(x<0) {putchar('-');x=-x;}
    if(x>=10) {
        out(x/10);
    }
    putchar('0'+x%10);
}
int que[MAXN],hd,tl;
int n;
ll val[MAXN],dp[MAXN],sum[MAXN],X[MAXN],Y[MAXN],a,b,c;
ll calc(int l,int z) {
    return dp[l]+a*sum[l]*sum[l]-2*a*sum[z]*sum[l]-b*sum[l];
}
bool slope(int l,int z,int s) {
    return (X[l]-X[s])*(Y[z]-Y[s])-(X[z]-X[s])*(Y[l]-Y[s])>=0;
}
void solve() {
    n=read();
    a=read();b=read();c=read();
    siji(i,1,n) {
        val[i]=read();
        sum[i]=sum[i-1]+val[i];
    }
    que[hd=tl=1]=0;
    siji(i,1,n) {
        while(hd<tl && calc(que[hd],i)<=calc(que[hd+1],i)) ++hd;
        dp[i]=calc(que[hd],i)+a*sum[i]*sum[i]+b*sum[i]+c;
        X[i]=sum[i];
        Y[i]=dp[i]+a*sum[i]*sum[i]-b*sum[i];
        while(hd<tl && slope(que[tl],i,que[tl-1])) --tl;
        que[++tl]=i;
    }
    printf("%lld\n",dp[n]);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif  
    solve();
}

BZOJ 1492: [NOI2007]货币兑换Cash

Description

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下
简称B券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，
两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券和 B券的
价值分别为 AK 和 BK（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法
。比例交易法分为两个方面：（a）卖出金券：顾客提供一个 [0,100] 内的实数 OP 作为卖出比例，其意义为：将
OP% 的 A券和 OP% 的 B券以当时的价值兑换为人民币；（b）买入金券：顾客支付 IP 元人民币，交易所将会兑
换给用户总价值为 IP 的金券，并且，满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK；例如，假定接
下来 3 天内的 Ak、Bk、RateK 的变化分别为：
假定在第一天时，用户手中有 100元人民币但是没有任何金券。用户可以执行以下的操作：
注意到，同一天内可以进行多次操作。小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经
知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来，如果开始时拥有S元钱，那么N天后最多能
够获得多少元钱。

Input

输入第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、B
K、RateK，意义如题目中所述。对于100%的测试数据，满足：0 0^9。

【提示】

1.输入文件可能很大，请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足：
每次买进操作使用完所有的人民币；
每次卖出操作卖出所有的金券。

Output

只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

题解

这道题hint里面告诉了我们对于我们可以在某一天尽可能多的换成人民币和尽可能多的买入AB劵
然后这道题的斜率方程就可以出来，对于某一天换成最多人民币的价值
$f(x)=max\{a[i]*x(i)+b[i]*y(i)\}$
$a[i],b[i]$ 表示AB券的价值
$x(i)$ 表示第i天手头的钱可以换成多少A券， $y(i)$ 表示第i天手头的钱可以换成多少B券
然后我们发现斜率并不满足单调性。横坐标的增加也不满足单调性。
然后当然可以平衡树维护啦……但是我们有更加好写的cdq分治
cdq分治的思想就是我们把这一段需要处理的区间从中点分成左右两份
一份是 $[l,mid]$ 一份是 $[mid+1,r]$
我们先处理左区间，左区间的每个点肯定都是能更新右区间的，我们将左区间的点维护成一个上凸壳，因为是求最大值
将右区间的直线的斜率排序，从大到小排（当然这个排序可以一开始就处理好），从前往后更新，就像斜率和凸壳都满足单调性的时候那样更新
这样我们平均每个节点会被它之前的节点更新 $\log n$ 次这样复杂度就是 $O(n \log n)$ 的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
#define mod 1000000007
//#define ivorysi
using namespace std;
typedef long long ll;
ll read() {
    ll res=0,neg=1;
    char c=getchar();
    while(c<'0' || c>'9') {
    if(c=='-') neg=-1;
    c=getchar();
    }
    while(c>='0' && c<='9') {
    res=res*10+c-'0';
    c=getchar();
    }
    return res*neg;
}
int qry[MAXN],n,tmp[MAXN],s;
double a[MAXN],b[MAXN],rate[MAXN];
struct node {
    double x,y;
    bool operator < (const node &b) {
        return x<b.x || (x==b.x && y<b.y);
    }
}que[MAXN],p[MAXN];
double dp[MAXN],ans;
bool cmp(int x,int y) {
    return a[x]*b[y]<a[y]*b[x];
}
bool slope(node l,node z,node s) {
    return (l.x-s.x)*(z.y-s.y)-(l.y-s.y)*(z.x-s.x) >=0.0;
}
double calc(node l,int z) {
    return l.x*a[z]+l.y*b[z];
}
void Cdqsolve(int l,int r) {
    if(l==r) {
        dp[l]=max(dp[l],dp[l-1]);
        ans=max(dp[l],ans);
        p[l].y=dp[l]/(a[l]*rate[l]+b[l]);
        p[l].x=p[l].y*rate[l];
        return;
    }
    int mid=(l+r)>>1;
    int idx1=l,idx2=mid+1,head=1,tail=0;
    siji(i,l,r) {
        if(qry[i]<=mid) tmp[idx1++]=qry[i];
        else tmp[idx2++]=qry[i];
    }
    siji(i,l,r) qry[i]=tmp[i];
    Cdqsolve(l,mid);
    siji(i,l,mid) {
        while(head<tail && slope(que[tail-1],que[tail],p[i])) --tail;
        que[++tail]=p[i];
    }
    siji(i,mid+1,r) {
        while(head<tail && calc(que[head],qry[i])<calc(que[head+1],qry[i])) ++head;
        dp[qry[i]]=max(dp[qry[i]],calc(que[head],qry[i]));
    }
    Cdqsolve(mid+1,r);
    if(l==1 && r==n) return;
    idx1=l,idx2=mid+1;
    head=l;
    while(head<=r) {
        if(idx2>r || (idx1<=mid && p[idx1]<p[idx2])) que[head++]=p[idx1++];
        else que[head++]=p[idx2++];
    }
    siji(i,l,r) {
        p[i]=que[i];
    }
    return;
}
void trans() {
    n=read();s=read();
    dp[0]=s;
    siji(i,1,n) {
        scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
        qry[i]=i;
    }
    sort(qry+1,qry+n+1,cmp);
    Cdqsolve(1,n);
    printf("%.3lf\n",ans);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    trans();
}