线段树优化dp,待做

poj3171
lightoj 1415
bzoj1835
uestc 1501
poj2376
poj2374
zjoi2010
fafu1231 http://acm.fafu.edu.cn/problem.php?id=1231
poj2355
hdoj4719
uestc1558
接下来要深入学习不单调的斜率优化dp,线段树深入,线性规划,分数规划,还有splay和可持久化的一些数据结构

hdoj3698 Let the light guide us——线段树优化dp

终于ac了,好久不写线段树,成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新,求区间最小值(包括历史值在内的最小值)。
dp[i][j]:前i行,且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m,超时
其实对于确定的i,j可以选择哪些k呢?abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心,f[i][j]为半径的区间和以k为中心,f[i-1][k]为半径的区间的重合部分,so。。求解每个阶段的时候,可以建立线段树[1,m],然后不断加入上个阶段的dp值,dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])],线段树维护最小值,注意lazy字段,lazy表示要往下更新的最小值,但是子孙节点的lazy有可能是小于它的(加入先对父区间更新为10,然后左子区间更新为8,这时候子区间的lazy就要比父区间小了),所以pushdown的时候,只有儿子节点的lazy没值或者小于父节点的lazy,才能重写这个儿子节点的lazy,否则可能导致结果偏大

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 110
#define maxm 5020
#define inf (0x3f3f3f3f)*2
int cost[maxn][maxm],f[maxn][maxm],dp[maxn][maxm];
int x[4*maxm];
int lazy[4*maxm];
int n,m;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id)
{
    x[id]=min(x[lson],x[rson]);
    return;
}
void pushdown(int id)
{
    if(lazy[id]==-1) return;
    if(lazy[lson]==-1 || lazy[id]<lazy[lson])
    {
        lazy[lson]=lazy[id];
    }
    if(lazy[rson]==-1 || lazy[id]<lazy[rson])
    {
        lazy[rson]=lazy[id];
    }
    x[lson]=min(x[lson],lazy[id]);
    x[rson]=min(x[rson],lazy[id]);
    lazy[id]=-1;
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        x[id]=min(x[id],v);
        if(lazy[id]==-1 || v<lazy[id]) lazy[id]=v;
        return;
    }
    pushdown(id);
    int mid=l+(r-l)/2;
    if(L<=mid) update(lson,l,mid,L,R,v);
    if(R>mid) update(rson,mid+1,r,L,R,v);
    pushup(id);
    return;
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return x[id];
    pushdown(id);
    int mid=l+(r-l)/2,ret=inf;
    if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
    if(R>=mid+1) ret=min(ret,query(rson,mid+1,r,L,R));
    return ret;
}
int solve()
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        memset(x,inf,sizeof(int)*(4*m+10));
        memset(lazy,-1,sizeof(int)*(4*m+10));
        for(j=1;j<=m;j++)
            update(1,1,m,max(1,j-f[i-1][j]),min(m,j+f[i-1][j]),dp[i-1][j]);
        for(j=1;j<=m;j++)
            dp[i][j]=cost[i][j]+query(1,1,m,max(1,j-f[i][j]),min(m,j+f[i][j]));
    }
    int ret=inf;
    for(i=1;i<=m;i++) ret=min(ret,dp[n][i]);
    return ret;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&cost[i][j]);
                dp[i][j]=(i==1?cost[i][j]:inf);
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&f[i][j]);
        printf("%d\n",solve());
    }
    return 0;
}

斯坦纳树相关

1.复杂度 O(n*3^k+cE*2^k)

c为SPFA复杂度中的常数,E为边的数量,但几乎达不到全部边的数量,甚至非常小。3^k来自于子集的转移sum{C(i,n)*2^i} (1<=i<=n),用二项式展开求一下和。

2.如果最后可以是森林,最后还要dp一次,f[state]表示状态为state时的最小花费,首先

for(j=0;j<(1<<cc+1);j++)
    for(i=1;i<=n;i++)
        f[j]=min(f[j],dp[i][j]);

表示最后是一棵树的情况。然后
 

for(j=1;j<(1<<cc+1);j++)
{
    for(sub=(j-1)&j;sub;sub=(sub-1)&j)
    {
        if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
        f[j]=min(f[j],f[sub]+f[j-sub]);
    }
}

表示有一些独立的斯坦纳树组合,这些子集枚举时往往对state有约束条件,需要check。最后的答案state往往也有约束条件。

 
hdoj3311 Dig The Wells
加一个点0,向各个点连边,权为各个点挖井的费用,求包含n个和尚和0点的最小斯坦纳树。这样就解决了边权的问题

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 2010
#define K 8
#define maxe 20000+10
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,p;
int dp[maxn][1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void init()
{
    int i,j;
    memset(dp,inf,sizeof(dp));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    for(i=0;i<=n;i++) st[i]=(1<<i);
    for(i=0;i<=n+m;i++)
        dp[i][st[i]]=0;
    return;
}
bool update(int &a,int b)
{
    if(b<a) {a=b;return 1;}
    return 0;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
void SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<n+1);j++)
    {
        for(i=0;i<=n+m;i++)
        {
            bool flag=1;
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];
                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                flag=update(dp[i][j],dp[i][x]+dp[i][y]);
            }
            //if(!flag) continue;
            if(dp[i][j]<inf)
            q.push(i),in[i][j]=1;
        }
        spfa(j);
    }
}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n+m;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(0,i,tmp);add(i,0,tmp);
        }
        for(i=1;i<=p;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        SteinerTree();
        int ans=inf;
        for(i=0;i<=n+m;i++)
            if(dp[i][(1<<n+1)-1]<ans) ans=dp[i][(1<<n+1)-1];
        printf("%d\n",ans);
    }
    return 0;
}

hdoj4085 Peach Blossom Spring
最后可能是森林,还要dp一次

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 60
#define K 13
#define maxe 3000+10
#define inf 0x3f3f3f3f//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,k;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void init()
{
    int i;
    memset(dp,inf,sizeof(dp));
    memset(f,inf,sizeof(f));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    for(i=1;i<=k;i++) st[i]=(1<<i-1);
    for(i=n-k+1;i<=n;i++) st[i]=(1<<i-n+k+k-1);
    for(int i=1;i<=n;i++)
        dp[i][st[i]]=0;
    return;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
bool check(int state)
{
    int i,j;
    int cnt=0;
    for(i=0;i<k;i++)
    {
        if(state&(1<<i)) cnt++;
        if(state&(1<<i+k)) cnt--;
    }
    return cnt==0;
}
int SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<(2*k));j++)
    {
        for(i=1;i<=n;i++)
        {
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];

                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
            }
            if(dp[i][j]>=inf) continue;
            q.push(i);in[i][j]=1;
        }
        spfa(j);
    }
    for(j=0;j<(1<<2*k);j++)
        for(i=1;i<=n;i++)
            f[j]=min(f[j],dp[i][j]);
    for(j=1;j<(1<<2*k);j++)
    {
        for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            if(check(sub) && check(j-sub))
                f[j]=min(f[j],f[sub]+f[j-sub]);
    }
    return f[(1<<2*k)-1];
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        int ans=SteinerTree();
        if(ans>=inf) printf("No solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

zoj3613 Wormhole Transport
同样最后可能是森林,要dp一次
注意check函数,合法条件是资源数>=工厂数,最后的最大工厂数取决于集合中资源数

#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 210
#define K 10
#define maxe 20000+10
#define inf (0x3f3f3f3f)*2//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
    int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
int p[maxn],s[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
int bit[10],cc;
void init()
{
    int i;
    memset(dp,inf,sizeof(dp));
    memset(f,inf,sizeof(f));
    memset(st,0,sizeof(st));
    memset(in,0,sizeof(in));
    //记得对关键点的st[]赋权
    cc=-1;
    for(i=1;i<=n;i++)
    {
        if(p[i] || s[i]){ cc++;st[i]=(1<<cc);bit[cc]=i;}
    }
    for(i=1;i<=n;i++)
        dp[i][st[i]]=0;
    return;
}
void spfa(int state)
{
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u][state]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            int state2=state|st[v];
            if(dp[u][state]+w<dp[v][state2])
            {
                dp[v][state2]=dp[u][state]+w;
                if(state2!=state || in[v][state]) continue;
                in[v][state]=1;q.push(v);
            }
        }
    }
    return;
}
bool check(int state)
{
    int i,tmp1=0,tmp2=0;
    for(i=0;i<=cc;i++)
    {
        if(state&(1<<i))
            tmp1+=p[bit[i]],tmp2+=s[bit[i]];
    }
    return tmp1>=tmp2;
}
void SteinerTree()
{
    int i,j,sub;
    for(j=1;j<(1<<cc+1);j++)
    {
        for(i=1;i<=n;i++)
        {
            if(st[i] && (st[i]&j)==0) continue;
            for(sub=(j-1)&j;sub;sub=(sub-1)&j)
            {
                int x=sub|st[i],y=(j-sub)|st[i];
                if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
                dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
            }
            if(dp[i][j]>=inf) continue;
            q.push(i);in[i][j]=1;
        }
        spfa(j);
    }
    for(j=0;j<(1<<cc+1);j++)
        for(i=1;i<=n;i++)
            f[j]=min(f[j],dp[i][j]);
    for(j=1;j<(1<<cc+1);j++)
    {
        for(sub=(j-1)&j;sub;sub=(sub-1)&j)
        {
            if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
            f[j]=min(f[j],f[sub]+f[j-sub]);
        }
    }
}
int cal(int state)
{
    int i,j,ans=0;
    for(i=0;i<=cc;i++)
    {
        if(state&(1<<i))
            ans+=s[bit[i]];
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v,w;
    while(~scanf("%d",&n))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(p,0,sizeof(p));memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i],&s[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        init();
        SteinerTree();
        int ans=0,cost=0;
        for(j=0;j<(1<<cc+1);j++)
        {
            if(!check(j) || f[j]>=inf) continue;
            int tmp=cal(j);
            if(tmp>ans)
            {
                ans=tmp;
                cost=f[j];
            }
            else if(tmp==ans && f[j]<cost) cost=f[j];
        }
        printf("%d %d\n",ans,cost);





    }
    return 0;
}

hdoj3401 Trade

单调队列优化dp,太菜了做不出来啊,看了题解才ok

dp[i][j]表示第i天有j张股票的最大money

dp[i][j]=max{dp[i-1][j],dp[i-w-1][k]-ap[i]*(j-k),dp[i-w-1][k]+bp[i]*(k-j)}

其中第二个决策表示买入股票,第三个决策表示卖出股票

复杂度太高需需优化

考虑第二个决策:dp[i-w-1][k]-ap[i]*(j-k)=dp[i-w-1][k]+ap[i]*k-ap[i]*j

可见对于dp[i][j],要找的是dp[i-w-1][k]+ap[i]*k的最大值,因为ap[i]*j在当前阶段和状态确定后是常数。用单调队列将决策那一维优化到O(n)

第三个决策也可以这样考虑

 

#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int ap[2010],bp[2010],as[2010],bs[2010],dp[2010][2010],q[2010],num[2010],head,tail;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int main()
{
    int i,j,T;
    int t,maxp,w;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&t,&maxp,&w);
        for(i=1;i<=t;i++) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        memset(dp,-inf,sizeof(dp));
        for(i=1;i<=1+w;i++)
        {
            for(j=0;j<=min(maxp,as[i]);j++)
                dp[i][j]=-ap[i]*j;
        }
        for(i=2;i<=t;i++)
        {
            for(j=0;j<=maxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
            head=0;tail=-1;
            for(j=0;j<=maxp;j++)
            {
                int bound=max(0,j-as[i]);
                while(head<=tail && num[head]<bound) head++;
                if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-ap[i]*j);
                int tmp=i-w-1<0?0:i-w-1;
                while(head<=tail && dp[tmp][j]+ap[i]*j>=q[tail]) tail--;
                q[++tail]=dp[tmp][j]+ap[i]*j;num[tail]=j;
            }
            head=0;tail=-1;
            for(j=maxp;j>=0;j--)
            {
                int bound=min(maxp,j+bs[i]);
                while(head<=tail && num[head]>bound) head++;
                if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-bp[i]*j);
                int tmp=i-w-1<0?0:i-w-1;
                while(head<=tail && dp[tmp][j]+bp[i]*j>=q[tail]) tail--;
                q[++tail]=dp[tmp][j]+bp[i]*j;num[tail]=j;
            }
        }
        int ans=dp[t][0];
        for(i=1;i<=maxp;i++)
            if(dp[t][i]>ans) ans=dp[t][i];
        printf("%d\n",ans);
    }
    return 0;
}

hdoj4122 Alice’s mooncake shop

哎,一道简单的单调队列比赛时候居然没做出来,很不应该。

假设第i小时定的月饼在第j小时或第k小时制作,那么j和k哪个更优呢?

(i-j)*s+cost[j]<(i-k)*s+cost[k]=====》cost[j]-j*s<cost[k]-k*s

可见,对于第i小时定的月饼用哪个决策与i无关:i choose min{cost[j]-j*s}其中i-T<=j<=i

区间最值,下界非递减,显然是单调队列。。

注意可能有两个及两个以上订单在同一小时。。

 

#include<stdio.h>
#include<string.h>
#include<map>
#include<string>
using namespace std;
typedef __int64 ll;
const int maxm=1e5+10;
map<string,int> mon;
ll num[maxm],cost[maxm];
ll cc[15];
bool is(ll year)
{
    if((year%100 && year%4==0) || (year%400==0)) return 1;
    return 0;
}
void cal(string m,ll date,ll year,ll h,ll r)
{
    int i,j;
    ll tmp=0;
    for(i=2000;i<=year-1;i++) tmp+=(is(i)?366:365);
    for(i=1;i<=mon[m]-1;i++) tmp+=((is(year)&&(i==2))?29:cc[i]);
    tmp+=date-1;tmp=tmp*24+h+1;
    num[tmp]+=r;
    return;
}
ll q[maxm],flag[maxm];
int head,tail;
int main()
{
    int i,j;
    ll n,m;
    mon["Jan"]=1;mon["Feb"]=2;mon["Mar"]=3;mon["Apr"]=4;mon["May"]=5;mon["Jun"]=6;mon["Jul"]=7;mon["Aug"]=8;mon["Sep"]=9;mon["Oct"]=10;mon["Nov"]=11;mon["Dec"]=12;
    cc[1]=31;cc[2]=28;cc[3]=31;cc[4]=30;cc[5]=31;cc[6]=30;cc[7]=31;cc[8]=31;cc[9]=30;cc[10]=31;cc[11]=30;cc[12]=31;
    while(~scanf("%I64d%I64d",&n,&m) && !(n==0 && m==0))
    {
        char month[5];ll date,year,h,r;
        memset(num,0,sizeof(ll)*(m+3));
        for(i=1;i<=n;i++)
        {
            scanf("%s%I64d%I64d%I64d%I64d",month,&date,&year,&h,&r);
            cal((string)month,date,year,h,r);
        }
        ll T,S;
        scanf("%I64d%I64d",&T,&S);
        for(i=1;i<=m;i++) scanf("%I64d",&cost[i]);
        ll ans=0;head=0;tail=-1;
        for(i=1;i<=m;i++)
        {
            while(head<=tail && q[tail]>=cost[i]-i*S) tail--;
            q[++tail]=cost[i]-i*S;flag[tail]=(ll)i;
            while(head<=tail && flag[head]<(ll)(i-T)) head++;
            if(num[i]==0) continue;
            ans+=(q[head]+i*S)*num[i];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdoj3507 Print Article

比较水的斜率优化dp
dp[i]:前i个词的最小cost
s[i]:前i个词的cost之和
w[j,i]:把第j到i个词分在一行的cost
dp[i]=min{dp[j]+w[j+1,i]}(0<=j<=i-1)
其中w[j,i]=(s[i]-s[j])^2+m
dp[i]的是式子展开:dp[i]=min{dp[j]+s[j]^2-2s[i]*s[j]}+s[i]^2+m
k=2s[i]
x=s[j]
y=dp[j]+s[j]^2
点的横坐标非递减,所以可以用单调队列维护凸壳,因为斜率非递减(即决策单调),所以可以均摊O(1)的求出最优决策是哪个,总复杂度O(n)
//////////////////
关于决策单调的另一种严格证明:
即证明w[i,j]满足四边形不等式:对于i<i’<j’<j,w[i,j']+w[i',j]<=w[i,j]+w[i',j']
(s[j']-s[i])^2+(s[j]-s[i'])^2<=(s[j]-s[i])^2+(s[j']-s[i'])^2
继续化简:-2s[i]s[j']-2s[i']s[j]<=-2s[i]s[j]-2s[i']s[j']
s[i]s[j']+s[i']s[j]>=s[i]s[j]+s[i']s[j']
(s[i']-s[i])(s[j]-s[j'])>=0
因为i<i’<j’<j,(s[i']-s[i])(s[j]-s[j'])>=0显然成立,所以w[i,j]满足四边形不等式,决策单调

#include<stdio.h>
#include<string.h>
int const maxn=5e5+10;
double const eps=1e-8;
typedef struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
}Point;
Point operator -(const Point &a,const Point &b)
{
    return Point(a.x-b.x,a.y-b.y);
}
int s[maxn],dp[maxn];
int n,m;
int head,tail;
Point q[maxn];
int cal(Point a,int k)
{
    return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
    Point p1=b-a,p2=c-b;
    return (double)(p1.y/(p1.x+eps))<(double)(p2.y/(p2.x+eps));
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        s[0]=0;dp[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&j);
            s[i]=s[i-1]+j;
        }
        head=tail=0;
        q[0]=Point(0,0);
        for(i=1;i<=n;i++)
        {
            int k=-2*s[i];
            while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
            dp[i]=cal(q[head],k)+s[i]*s[i]+m;
            Point p(s[i],dp[i]+s[i]*s[i]);
            while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
            q[++tail]=p;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

hdoj2829 Lawrence

我擦。。去掉一个语句居然就ac了,纠结n久。这题貌似不用斜率有优化,用四边形不等式优化也行。具体明天再说。。
第一道状态是二维,决策一维的斜率优化dp,其实和状态一维的差不多,无非多了层外层循环。每个阶段都用一下单调队列。。

#include<stdio.h>
#include<string.h>
const int maxn=1010;
const int inf=0x3f3f3f3f;
typedef struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y)
    {
        x=_x;y=_y;
    }
}Point;
Point operator -(const Point &a,const Point &b)
{
    return Point(a.x-b.x,a.y-b.y);
}
int cal(Point a,int k)
{
    return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
    Point p1=b-a,p2=c-b;
    return (p1.y*1.0/p1.x)<(p2.y*1.0/p2.x);
}
Point q[maxn];
int s[maxn],c[maxn],dp[maxn][maxn];
int head,tail,n,m;
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        c[0]=s[0]=0;
        for(i=1;i<=n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            s[i]=s[i-1]+tmp;
            c[i]=c[i-1]+tmp*s[i];
        }
        memset(dp,0,sizeof(dp));
        for(j=1;j<=n;j++) dp[1][j]=0;
        for(i=1;i<=n;i++)
            dp[i][1]=s[i]*s[i]-c[i];
        for(j=2;j<=m+1;j++)
        {
            head=tail=0;
            q[0]=Point(s[1],dp[1][j-1]+c[1]);
            for(i=2;i<=n;i++)
            {
                //if(i<j+1) continue;
                int k=-s[i];
                while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
                dp[i][j]=cal(q[head],k)+s[i]*s[i-1]-c[i-1];
                Point p(s[i],dp[i][j-1]+c[i]);
                while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
                q[++tail]=p;
            }
        }
        printf("%d\n",dp[n][m+1]);



    }
    return 0;
}

bzoj1010 玩具装箱toy

斜率优化dp第一题,纠结了n久。。最后输出改成%I64d就PE,要%lld才能ac,而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp,记下几点:
(1)求最大值,维护上凸壳;求最小值,维护下凸壳;
(2)当点的横坐标单调,且斜率单调时,此时决策是单调的(即满足四边形不等式),可以用单调队列从前往后找最优决策(怎么找?只有最优决策点的值比两侧都要优,注意只有二字),找到之后前面的都是无用决策了,插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的,而斜率不单调,这时候决策是不单调的,但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1 那么显然此时直线簇的斜率k满足k1 (4)当点的横坐标不单调且直线斜率不单调的时候。如果用单调队列,那么求最优决策点还是可以二分。当插入一个点的时候,我们首先根据它的横坐标二分出它的插入位置,然后维护凸壳,但是由于可能插入在队列中间,两边都要删点,复杂度过高。
正确做法是用平衡树维护动态凸壳。(我擦,说着简单,写着蛋疼无比)(这种情况细节还不太会,有待学习)

#include<stdio.h>
typedef long long ll;
const int maxn=5e4+10;
typedef struct Node{
    ll x,y;
}Node;
Node q[maxn];
int n;
ll s[maxn],L,dp[maxn];
int head,tail;
ll cal(ll x,ll y,ll k)
{
    return y-2*k*x;
}
bool xielv(Node a,Node b,Node c)
{
    ll x1=a.x,y1=a.y,x2=b.x,y2=b.y,x3=c.x,y3=c.y;
    return (y2-y1)*(x3-x2)<(y3-y2)*(x2-x1);
}
int main()
{
    int i,j;
    while(~scanf("%d%lld",&n,&L))
    {
        s[0]=0;dp[0]=0;
        ll tmp;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&tmp);s[i]=s[i-1]+tmp;
        }
        head=tail=0;q[0].x=0;q[0].y=0;
        for(i=1;i<=n;i++)
        {
            ll k=s[i]+i-1-L,x,y;
            while(head<tail && cal(q[head].x,q[head].y,k)>=cal(q[head+1].x,q[head+1].y,k))
                head++;
            dp[i]=cal(q[head].x,q[head].y,k)+k*k;
            x=s[i]+i;y=dp[i]+x*x;
            Node tt;tt.x=x;tt.y=y;
            while(head<tail && !xielv(q[tail-1],q[tail],tt))
                tail--;
            q[++tail]=tt;
        }
        printf("%lld\n",dp[n]);
    }
    return 0;
}

hdoj2993 MAX Average Problem

这篇论文里的例二:http://www.docin.com/p-47950655.html
分析不写了,论文里写的很清楚,虽说不是斜率优化dp,但应该也可以算是斜率优化dp的入门题了。。记得加外挂哦~~

#include<stdio.h>
#include<string.h>
const int maxn=1e5+10;
int a[maxn],s[maxn];
int q[maxn],head,tail;
double cal(int i,int j)
{
    return (double)(s[i]-s[j])/(double)(i-j);
}
void scan(int &num)//对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-');
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');//去负号后空格
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}
int main()
{
    int i,j;
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        s[0]=0;
        for(i=1;i<=n;i++)
        {
            scan(a[i]);
            s[i]=s[i-1]+a[i];
        }
        head=tail=0;
        q[0]=0;
        double maxx=0;
        for(i=k;i<=n;i++)
        {
            while(head<tail && cal(i,q[head])<=cal(i,q[head+1]))
                head++;
            double tmp=cal(i,q[head]);
            if(tmp>maxx) maxx=tmp;
            while(head<tail && cal(q[tail],q[tail-1])>=cal(i-k+1,q[tail]))
                tail--;
            q[++tail]=i-k+1;
        }
        printf("%.2f\n",maxx);
    }
    return 0;
}

poj3017 Cut the Sequence

单调队列+treap
会爆栈,要c++扩栈。
题意:给出n个数(n<=10^5),给出m,要求将数列分成连续的若干段,使得每段之和<=m,且每段中的最大值的和最小,求这个最小的和
分析:
很容易得到:dp[i]=min{dp[j]+max{a[j+1……i]}|bound[i]<=j<=i-1},其中bound[i]是使得sigma(a[j+1]……a[i])<=m的最大下标,可以二分得到。
状态数O(n),转移O(n),显然要优化。
由于bound[i]是随着i的增大单调不降的,而且一个点j要成为i的最优决策首先必须满足a[j]比a[j+1……i]都要大(这点还不明白)。那么我们可以用单调队列维护。
现在对于确定的决策j,我们可以O(1)时间知道a[j+1]~a[i]的最大值(若q[p]=a[j],那么max{a[j+1]~a[i]}=q[p+1],q[p+1]存在的前提下),但是对于状态i,当前单调队列的队首元素的原始下标不一定就是最优决策值,所以我们要找到一种数据结构动态的维护dp[j]+max{a[j+1]~a[i]},其中a[j]是当前单调队列中的元素。那么显然当状态转移的时候需要对这种数据结构插入、删除、求最小值。显然这种数据结构应当是平衡树为好。
思路还是很清晰的,但是要注意细节,队列中的元素个数要时刻清晰,插入删除了哪些决策下的答案要清楚。还有就是对于决策是bound这种情况,要特判。因为我代码里面的单调队列都是从bound+1开始的元素。

#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef long long ll;
const int maxn=1e6+10;
typedef struct Node{
    Node *ch[2];
    int r;
    ll v;
    int s;
    int cc;
    Node(){}
    Node(int v):v(v) {ch[0]=ch[1]=NULL;r=rand();s=1;cc=1;}
    void init(ll _v)
    {
        v=_v;
        ch[0]=ch[1]=NULL;r=rand()%1000007;s=1;cc=1;
        return;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(ll x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node pool[maxn];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,ll x)
{
    if(o==NULL)
    {
        o=&pool[cnt++];
        o->init(x);
    }
    else
    {
        int d=o->cmp(x);
        if(d==-1) o->cc++;
        else
        {
            insert(o->ch[d],x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
void remove(Node* &o,ll x)
{
    int d=o->cmp(x);
    if(d==-1 && o->cc>1)
        o->cc--;
    else if(d==-1)
    {
        if(o->ch[0]!=NULL && o->ch[1]!=NULL)
        {
            int d2=(*(o->ch[1])<*(o->ch[0])?1:0);
            rotate(o,d2);remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
        }
    }
    else remove(o->ch[d],x);
    if(o!=NULL) o->maintain();
}
ll kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc) return o->v;
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
ll a[maxn],s[maxn];
int head,tail,num[maxn];
ll q[maxn];
ll dp[maxn];
int n;
ll m;
int bsearch(int i,int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(s[i]-s[mid]<=m) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
    srand((unsigned int)time(NULL));
    int i,j;
    scanf("%d%lld",&n,&m);
        bool flag=1;
        cnt=0;s[0]=0;dp[0]=0;
        Node* root=NULL;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            s[i]=s[i-1]+a[i];
            if(a[i]>m) flag=0;
        }
        if(flag==0)
        {
            printf("-1\n");return 0;
        }
        head=tail=0;
        q[tail]=0;num[0]=0;
        for(i=1;i<=n;i++)
        {
            int bound=bsearch(i,0,i-1);bound++;
            while(head<=tail && num[head]<bound)
            {
                if(tail>head)
                {
                    remove(root,dp[num[head]]+q[head+1]);
                }
                head++;
            }
            while(head<=tail && a[i]>=q[tail])
            {
                if(tail-1>=head) remove(root,dp[num[tail-1]]+q[tail]);
                tail--;
            }
            q[++tail]=a[i];num[tail]=i;
            int tmp=q[head];
            if(head==tail)
            {
                dp[i]=dp[bound-1]+tmp;
                continue;
            }
            insert(root,dp[num[tail-1]]+a[i]);
            dp[i]=kth2(root,root->s);
            if(dp[bound-1]+tmp<dp[i]) dp[i]=dp[bound-1]+tmp;
        }
        printf("%lld\n",dp[n]);
    return 0;
}



hdoj4557 非诚勿扰

居然0ms,数据略水。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
const int maxn=1e3+10;
typedef struct Node{
    Node *ch[2];
    char name[1004][17];
    int head,tail;
    int r;
    int v;
    int s;
    int cc;
    Node(){}
    Node(int v):v(v) {ch[0]=ch[1]=NULL;r=rand();s=1;cc=1;}
    void init(char str[],int _v)
    {
        v=_v;head=tail=0;
        strcpy(name[head],str);
        ch[0]=ch[1]=NULL;r=rand()%10007;s=1;cc=1;
        return;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(int x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node*root=NULL;
Node pool[maxn];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,char s[],int x)
{
    if(o==NULL)
    {
        o=&pool[cnt++];
        o->init(s,x);
    }
    else
    {
        int d=o->cmp(x);
        if(d==-1)
        {
            o->cc++;
            int head=o->head,tail=o->tail;
            strcpy(o->name[++tail],s);
            o->tail++;
        }
        else
        {
            insert(o->ch[d],s,x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
void remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1 && o->cc>1)
    {
        o->cc--;
    }
    else if(d==-1)
    {
        if(o->ch[0]!=NULL && o->ch[1]!=NULL)
        {
            int d2=(*(o->ch[1])<*(o->ch[0])?1:0);
            rotate(o,d2);remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
        }
    }
    else remove(o->ch[d],x);
    if(o!=NULL) o->maintain();
}
int kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc)
    {
        printf("%s\n",o->name[o->head]);
        o->head++;
        remove(root,o->v);
    }
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
int rank2(Node* o,int x,bool &flag)
{
    int cnt=0;
    while(o!=NULL)
    {
        int d=o->cmp(x);
        if(d==-1)
        {
            if(o->ch[1]!=NULL) cnt+=o->ch[1]->s;
            return cnt+o->cc;
        }
        if(d==0)
        {
            cnt+=o->cc;
            if(o->ch[1]!=NULL) cnt+=(o->ch[1]->s);
            o=o->ch[0];
        }
        else o=o->ch[1];
    }
    flag=0;
    return cnt+1;
}
int main()
{
    srand((unsigned int)time(NULL));
    int T,cases=0;
    int i,j,tmp;
    scanf("%d",&T);
    while(T--)
    {
        int n;char s[10];
        cnt=0;root=NULL;
        scanf("%d",&n);
        printf("Case #%d:\n",++cases);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            if(strcmp(s,"Add")==0)
            {
                scanf("%s %d",s,&tmp);
                insert(root,s,tmp);
                printf("%d\n",root->s);
            }
            else
            {
                scanf("%d",&tmp);
                bool flag=1;
                int ans=rank2(root,tmp,flag);
                if(ans==1 && !flag) printf("WAIT...\n");
                else
                {
                    if(flag) kth2(root,ans);
                    else kth2(root,ans-1);
                }
            }
        }
    }
    return 0;
}

poj1442 Black Box

treap入门题

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
typedef struct Node{
    Node *ch[2];
    int r;
    int v;
    int s;
    int cc;
    Node(){}
    void init(int _v)
    {
        v = _v;
        ch[0] = ch[1] = NULL;r = rand()%100007;s=1;cc=1;
    }
    bool operator <(const Node& rhs) const
    {
        return r<rhs.r;
    }
    int cmp(int x) const
    {
        if(x==v) return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=cc;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}Node;
Node pool[4000000];
int cnt;
void rotate(Node* &o,int d)
{
    Node*k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
    o->maintain();k->maintain();o=k;
    return;
}
void insert(Node* &o,int x)
{
    if(o==NULL) {o=&pool[cnt++];o->init(x);}
    else
    {
        int d=o->cmp(x);
        if(d==-1) o->cc++;
        else
        {
            insert(o->ch[d],x);
            if(*(o)<*(o->ch[d])) rotate(o,d^1);
        }
    }
    o->maintain();
    return;
}
int kth2(Node* o,int k)//第k大数
{
    if(o==NULL || k<=0 || k>o->s) return 0;//k不合法时返回0
    int s=(o->ch[1]==NULL?0:o->ch[1]->s);
    if(s+1<=k && k<=s+o->cc) return o->v;
    else if(k<=s) return kth2(o->ch[1],k);
    else return kth2(o->ch[0],k-s-o->cc);
}
int a[30010],b[30010];
int main()
{
    int i,j;
    int n,m;
    srand((unsigned int)time(NULL));
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=m;i++) scanf("%d",&b[i]);
        cnt=0;
        int k=0;Node *root=NULL;
        int pre=1;
        for(i=1;i<=m;i++)
        {
            for(j=pre;j<=b[i];j++)
                insert(root,a[j]);
            pre=b[i]+1;
            k++;
            printf("%d\n",kth2(root,b[i]-k+1));

        }
    }
    return 0;
}

单调队列

fzoj1894 志愿者选拔
裸的单调队列,注意出队的时候,只有当当前删除的人的下标等于优先队列中队首的人的下标,才出队

#include<stdio.h>
#include<string.h>
char s[10];
int q[1000000+10],head,tail;
int num[1000000+10];
int main()
{
    int i,j,t,val;
    scanf("%d",&t);
    while(t--)
    {
        head=0;tail=-1;
        int index=0,index2=0;
        scanf("%s",s);
        while(~scanf("%s",s) && strcmp(s,"END")!=0)
        {
            if(s[0]=='C')
            {
                index++;
                scanf("%s %d",s,&val);
                while(tail>=head && val>=q[tail]) tail--;
                q[++tail]=val;num[tail]=index;
            }
            else if(s[0]=='G')
            {
                index2++;
                if(num[head]==index2) head++;
            }
            else
            {
                if(head>tail) puts("-1");
                else printf("%d\n",q[head]);
            }
        }
    }
    return 0;
}

poj2823 Sliding Window
经典的单调队列应用
f[x]=opt{a[i]|bound[x]<=i<=x}

#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int a[maxn],q[maxn];
int num[maxn];
int head,tail;
int main()
{
    int i,j;
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");

        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");



    }
    return 0;
}

hdoj3415 Max Sum of Max-K-sub-sequence
经典单调队列
dp[i]=sum[i]-sum[j]=sum[i]-min{sum[j]|i-k<=j<=i-1}
加输入外挂才能过,,不然TLE。。囧~

#include<stdio.h>
#include<string.h>
#define maxn 200000+10
int a[maxn],q[maxn],head,tail;
int num[maxn];
int path[maxn];
void scan(int &num)//对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-');
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');//去负号后空格
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}

int main()
{
    int i,j;
    int t,n,k;
    scan(t);
    while(t--)
    {
        scan(n);scan(k);
        head=0;tail=-1;
        a[0]=0;
        for(i=1;i<=n;i++) {scan(a[i]);a[i+n]=a[i];}
        for(i=1;i<=2*n;i++) a[i]+=a[i-1];
        q[++tail]=a[0];num[tail]=0;
        for(i=1;i<=2*n;i++)
        {
            while(num[head]<i-k) head++;
            path[i]=num[head]+1;
            while(head<=tail && a[i]<q[tail]) tail--;
            q[++tail]=a[i];num[tail]=i;
        }
        int ans=-1000000000,begin=maxn,end,len;
        for(i=1;i<=2*n;i++)
        {
            if(a[i]-a[path[i]-1]>ans)
            {
                ans=a[i]-a[path[i]-1];len=i-path[i]+1;
                begin=path[i]>n?path[i]-n:path[i];
                end=i>n?i-n:i;
            }
            else if(a[i]-a[path[i]-1]==ans)
            {
                if((path[i]>n?path[i]-n:path[i])<begin)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
                else if((path[i]>n?path[i]-n:path[i])==begin && i-path[i]+1<len)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
            }
        }
        printf("%d %d %d\n",ans,begin,end);


    }
    return 0;
}

钢之炼金术士FA的五首OP

终于看完钢炼FA了,有点不舍,动漫里确实塑造了一个全新的很棒的世界观啊
OP1 again
这首很怀旧

OP2 ホログラム
这首最喜欢,有一种给人带来动力的感觉,歌词也很好

OP3 ゴールデンタイムラバー
这首诗最燃的一首,听完有没有充满力量呢

OP4 Period
比较温暖柔和的曲调

OP5 レイン
故事要终了的旋律

ED5 RAY OF LIGHT
这首ED也不错