动态规划（二）

作者: 云中翻月 | 来源:发表于2019-07-27 23:35 被阅读0次

状态压缩DP

POJ 2441: Arrange the Bulls
$d[i,j]$ 表示前i头cow，目前畜栏使用情况为j的方案数。
初值： $d[0,0]=1$
转移方程： $d[i,j|(1<<k)]+=d[i-1,j]，(j \&(1<<k))==0$
目标： $∑d[n,j]$
ps：注意需要使用滚动数组防止MLE，加入剪枝（如果目前状态方案数为0则不转移）防止TLE，加入清空滚动数组的操作防止WA。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
d[i,j]表示前i头cow，目前畜栏使用情况为j的方案数。
初值：d[0,0]=1
转移方程：d[i,j|(1<<k)]+=d[i-1,j]，(j&(1<<k))==0 
目标：∑d[n,j]
ps：注意需要使用滚动数组防止MLE，加入剪枝（如果目前状态方案数为0则不转移）防止TLE，加入清空滚动数组的操作防止WA。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+2;
const int INF=0x3f3f3f3f;
int d[2][(1<<maxn)],n,m,ans=0;
vector<int>v[maxn];
void dp(){
    d[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=(1<<m)-1;j++){
            if(d[i-1&1][j]==0) continue; //强力剪枝 
            for(int k=0;k<v[i].size();k++){
                if((j&(1<<v[i][k]))==0){
                    d[i&1][j|(1<<v[i][k])]+=d[i-1&1][j];
                }
            }
            d[i-1&1][j]=0; //滚动数组记得清空 
        }
    }
    for(int i=0;i<=(1<<m)-1;i++) ans+=d[n&1][i];
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Arrange the Bulls.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        while(num--){
            int temp;
            cin>>temp;
            v[i].push_back(temp-1);
        }
    }
    dp();
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3254: Corn Fields
预处理出use数组表示可行的二进制数集合。
$d[i,j]$ 表示前i行，第i行状态为j的方案数。在保证第i行和第i-1行状态不矛盾且和土地使用条件不矛盾的情况下转移即可。
代码如下

/*
预处理出use数组表示可行的二进制数集合。 
d[i,j]表示前i行，第i行状态为j的方案数。在保证第i行和第i-1行状态不矛盾 且和土地使用条件不矛盾 的情况下转移即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=12+2;
const int INF=0x3f3f3f3f;
const int mod=100000000;
int d[maxn][(1<<maxn)],n,m,a[maxn][maxn],b[maxn],ans=0;
vector<int>use;
bool check(int x){
    int last=0;
    while(x){
        int now=x&1;
        x/=2;
        if(now==1&&last==1) return false;
        last=now;
    }
    return true;
}
void pre(){
    for(int i=0;i<(1<<m);i++){
        if(check(i)) use.push_back(i);
    }
}
bool check1(int x,int y){
    for(int i=0;i<m;i++){
        int temp1=x&(1<<i),temp2=y&(1<<i);
        if(temp1==1&&temp2==0) return false;
    }
    return true;
}
void dp(){
    d[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<use.size();j++){ //枚举i行 
            int now=use[j];
            if(now&b[i]) continue;
            for(int k=0;k<use.size();k++){ //枚举i-1行
                int last=use[k];
                if(last&now) continue; //上下有1相邻
                if(last&b[i-1]) continue;
//              if(!check1(now,b[i])&&!check1(last,b[i-1])) continue;
                d[i][now]+=d[i-1][last];
                d[i][now]%=mod;
            }
        }
    }
    for(int j=0;j<use.size();j++) ans+=d[n][use[j]],ans%=mod;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Corn Fields.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=m;j++){
            sum=sum*2+a[i][j];
        }
        b[i]=(1<<m)-1-sum; //压缩状态 某一位0表示可填 
//      D(b[i]);
    }
    pre();
    dp();
    cout<<ans;
    return 0;
}

POJ 2836: Rectangular Covering
任意两个点可以确定一个矩形。（分别作为左下角和右上角）于是预处理出所有这样n*n个矩形的覆盖点集和面积进行状态压缩dp。
$d[i]$ 表示目前覆盖状态为i的最小面积和。（注意重合的面积，重合几次就计算几次）
初值： $d[0]=0$ ，其他为INF
目标： $d[(1<<n)-1]$
转移方程： $d[j|c[i,k]]=min(d[j|c[i,k]],d[j]+s[i,k])$
其中
$c[i,j]$ 表示i点和j点分别作为左下角和右上角构成的矩形能够覆盖的点集。
$s[i,j]$ 表示i点和j点分别作为左下角和右上角构成的矩形的面积。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
任意两个点可以确定一个矩形。（分别作为左下角和右上角）于是预处理出所有这样n*n个矩形的覆盖点集和面积进行状态压缩dp。
d[i]表示目前覆盖状态为i的最小面积和。（注意重合的面积，重合几次就计算几次） 
初值：d[0]=0，其他为INF 
目标：d[(1<<n)-1]
转移方程：d[j|c[i][k]]=min(d[j|c[i][k]],d[j]+s[i][k])
其中 
c[i,j]表示i点和j点分别作为左下角和右上角构成的矩形能够覆盖的点集。 
s[i,j]表示i点和j点分别作为左下角和右上角构成的矩形的面积。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int INF=0x3f3f3f3f;
int n,x[maxn],y[maxn],d[(1<<maxn)],c[maxn][maxn],s[maxn][maxn];
//c[i,j]表示i点和j点分别作为左下角和右上角构成的矩形能够覆盖的点集 
//s[i,j]表示i点和j点分别作为左下角和右上角构成的矩形的面积 
void init(){
    memset(d,INF,sizeof(d));
}
int cal_c(int a,int b){
    int X1=min(x[a],x[b]);
    int X2=max(x[a],x[b]);
    int Y1=min(y[a],y[b]);
    int Y2=max(y[a],y[b]);
    int res=0;
    for(int i=1;i<=n;i++){
        if(x[i]>=X1&&x[i]<=X2&&y[i]>=Y1&&y[i]<=Y2) res|=1<<i-1;
    } 
    return res;
}
int cal_s(int a,int b){
    int dx=max(1,abs(x[a]-x[b]));
    int dy=max(1,abs(y[a]-y[b]));
    return dx*dy;
}
void pre(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            c[i][j]=cal_c(i,j);
            s[i][j]=cal_s(i,j);
        }
    }
}
void dp(){
    d[0]=0;
    for(int j=0;j<=(1<<n)-1;j++){
        for(int i=1;i<=n;i++){  
            if(j&(1<<i-1)) continue;
            for(int k=1;k<=n;k++){
                if(i==k) continue;
                d[j|c[i][k]]=min(d[j|c[i][k]],d[j]+s[i][k]);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Rectangular Covering.in","r",stdin);
    while(cin>>n){
        if(!n) break;
        for(int i=1;i<=n;i++) cin>>x[i]>>y[i];  
        init();
        pre();
        dp();
        cout<<d[(1<<n)-1]<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 1795: DNA Laboratory
题解链接：https://blog.csdn.net/qq_29169749/article/details/54755026
PS：注意dp中的顺序问题，详见注释。
代码如下

/*
题解链接：https://blog.csdn.net/qq_29169749/article/details/54755026
PS：注意dp中的顺序问题，详见注释。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=15+2;
const int INF=0x3f3f3f3f;
string str[maxn],ans;
int T,n,kase=0,cost[maxn][maxn],d[maxn][(1<<maxn)];
void init(){
    memset(cost,0,sizeof(cost));
}
void pre(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(str[i].find(str[j])!=string::npos){ //j包含于i 
                str[j]=str[i];
            }
        }
    }
    sort(str+1,str+n+1);
    n=unique(str+1,str+n+1)-str-1;
    /*
    for(int i=1;i<=n;i++){
        D(str[i]);E;
    }
    */
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            int len=min(str[i].length(),str[j].length());
            for(int k=len;k>=0;k--){ //k=0时没有重合 
                if(str[i].substr(str[i].length()-k)==str[j].substr(0,k)){
                    cost[i][j]=str[i].length()-k;
                    break;
                }
            }
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            D(cost[i][j]);
        }
        E;
    } 
    */
}
void dp(){
    memset(d,INF,sizeof(d));
    for(int i=1;i<=n;i++){
        d[i][1<<i-1]=str[i].length();
    }
    //注意这里的dp顺序，d[i][j|(1<<i-1)]来自d[k][j]。
    //所以k和j要在外层循环（k和j的顺序交换也影响，它们共同组成状态。除此以外i一定要在最内层）
    //关于j和k循环顺序的解释：
    //由于最优解不一定是按照字符串顺序添加的，所以不能优先枚举字符串。这和corn field和炮兵阵地一类的题目不一样。
    //（那类题目要按行dp，行就是“阶段”，所以要放在第一维循环） 
    for(int j=0;j<=(1<<n)-1;j++){
        for(int k=1;k<=n;k++){  
            if((j&(1<<k-1))==0) continue;
            if(d[k][j]==INF) continue;  
            for(int i=1;i<=n;i++){
                if(i==k) continue;
                if(j&(1<<i-1)) continue;
                d[i][j|(1<<i-1)]=min(d[i][j|(1<<i-1)],d[k][j]+cost[i][k]);
            }
        }
    }
    /*
    //如下这种循环写法是不可以的，外层循环必须是之前的状态，内层循坏才枚举当前状态。
    //（有些题目写反了不会出错，但这道题目会） 
    for(int i=1;i<=n;i++){
        for(int j=0;j<=(1<<n)-1;j++){
            if((j&(1<<i-1))==0) continue;
            for(int k=1;k<=n;k++){
                if(d[k][j&(~(1<<i-1))]==INF) continue;  
                if(i==k) continue;
                if(((j&(~(1<<i-1)))&(1<<k-1))==0) continue;
                d[i][j]=min(d[i][j],d[k][j&(~(1<<i-1))]+cost[i][k]);
            }
        }
    }
    */
//  for(int i=1;i<=n;i++) D(d[i][(1<<n)-1]);
//  E;
}
void dfs(int id,int s){
    if(s==0) return;
    string temp;
    int nxt_id=-1;
    for(int i=1;i<=n;i++){
        if(i==id) continue;
        if((s&(1<<i-1))==0) continue;
        if(d[id][s]!=d[i][s&~(1<<id-1)]+cost[id][i]) continue;
        string t=str[i].substr(str[id].length()-cost[id][i]);
        if(nxt_id==-1||t<temp){
            temp=t;nxt_id=i;
        }
    }
    ans+=temp;
    dfs(nxt_id,s&~(1<<id-1));
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("DNA Laboratory.in","r",stdin);
    cin>>T;
    while(T--){
        cout<<"Scenario #"<<++kase<<":"<<endl;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>str[i];
        if(n==1){
            cout<<str[1];
        }
        else{
            init();
            pre();
            dp();
            int id=1;
            for(int i=2;i<=n;i++){
                if(d[i][(1<<n)-1]<d[id][(1<<n)-1]){
                    id=i; //id为目标字符串最左边字符串在原字符串序列中的下标 
                }
            }
            ans=str[id];
//          cout<<ans<<endl;
            dfs(id,(1<<n)-1);
            cout<<ans;
        }
        cout<<endl<<endl;   
    }
    return 0;
}

POJ 3411: Paid Roads
dijkstra即可。
注意由于有些点可能会反复经过，所以第一维枚举难以有固定顺序，不能用循环来进行状态压缩dp。
代码如下

/*
dijkstra即可。
注意由于有些点可能会反复经过，所以第一维枚举难以有固定顺序，不能用循环来进行状态压缩dp。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+2;
const int INF=0x3f3f3f3f;
int n,m,vis[maxn][(1<<maxn)];
struct edge{
    int a,b,c,p,r;
}e[maxn];
struct node{
    int p,sta,c;
    bool operator<(const node& h)const{return c>h.c;}
};
priority_queue<node>q;
int bfs(){
    node nd;nd.c=0,nd.p=1,nd.sta=1;
//  q.push((node){1,1,0}); //POJ会ce 
    q.push(nd); 
    while(q.size()){
        node now=q.top();q.pop();
        if(now.p==n) return now.c;
        if(vis[now.p][now.sta]) continue;
        vis[now.p][now.sta]=1;
        for(int i=1;i<=m;i++){
            if(e[i].a!=now.p) continue;
            int dis=now.c+e[i].r;
            if((now.sta|(1<<e[i].b-1))&(1<<e[i].c-1)) dis=min(dis,now.c+e[i].p);
            node nd1;nd1.c=dis,nd1.p=e[i].b,nd1.sta=now.sta|(1<<e[i].b-1);
            q.push(nd1);
//          q.push((node){e[i].b,now.sta|(1<<e[i].b-1),dis});
        }
    }
    return INF;
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("Paid Roads.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].a>>e[i].b>>e[i].c>>e[i].p>>e[i].r;
    int ans=bfs();
    ans==INF?cout<<"impossible":cout<<ans;
    return 0;
}

矩阵的幂

POJ 3420: Quad Tiling
找规律发现：f(n)=f(n-1)+4f(n-2)+2f(n-3)+3f(n-4)+2f(n-5)+3f(n-6)+...
f(n)-f(n-2)=f(n-1)+4f(n-2)+f(n-3)-f(n-4)
即f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)
最后用矩阵优化递推即可。
注意找递推规律时，注意不重不漏的原则，不能让矩形可以从中分割出来成为两个独立的小部分。
ps：一个天坑在于，这个递推公式递推时，直接取模可能算出负数，所以要处理一下。
代码如下

/*
找规律发现：f(n)=f(n-1)+4f(n-2)+2f(n-3)+3f(n-4)+2f(n-5)+3f(n-6)+...
f(n)-f(n-2)=f(n-1)+4f(n-2)+f(n-3)-f(n-4)
即f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)
最后用矩阵优化递推即可。 
注意找递推规律时，注意不重不漏的原则，不能让矩形可以从中分割出来成为两个独立的小部分。 
ps：一个天坑在于，这个递推公式递推时，直接取模可能算出负数，所以要处理一下。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+5;
const int INF=0x3f3f3f3f;
int n,m,e[maxn][maxn],p=4,f[maxn];
void init(){
    memset(e,0,sizeof(e));
    e[1][1]=1;e[1][2]=5;e[1][3]=1;e[1][4]=-1;
    e[2][1]=1;e[3][2]=1;e[4][3]=1;
    f[1]=36%m;f[2]=11%m;f[3]=5%m;f[4]=1%m;
}
void mulself(int a[maxn][maxn],int b[maxn][maxn]){
    int temp[maxn][maxn]={0};
    for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) for(int k=1;k<=p;k++) temp[i][j]=(temp[i][j]+a[i][k]*b[k][j]%m+m)%m;//注意要先加m再取模 
    memcpy(a,temp,sizeof(temp));
}
void mul(int b[maxn][maxn],int a[maxn]){
    int temp[maxn]={0};
    for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) temp[i]=(temp[i]+b[i][j]*a[j]%m+m)%m;
    memcpy(a,temp,sizeof(temp));
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Quad Tiling.in","r",stdin);
    while(cin>>n>>m){
        if(!n&&!m) break;
        init(); 
        if(n<=4){
            cout<<f[4-n+1]<<endl;
            continue;
        }
        n-=4;
        while(n){
            if(n&1) mul(e,f);
            mulself(e,e);
            n>>=1;
        }
        cout<<f[1]<<endl;
    }
    return 0;
}

POJ 3735: Training little cats
题解链接：https://blog.csdn.net/wangjian8006/article/details/7884989
代码如下

/*
题解链接：https://blog.csdn.net/wangjian8006/article/details/7884989 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,k,p;
ll m,f[maxn],e[maxn][maxn]; //e为系数矩阵 
void pre(){
    memset(e,0,sizeof(e));
    memset(f,0,sizeof(f));
    for(int i=1;i<=p;i++) e[i][i]=1;
    f[p]=1;
}
void mul(ll b[maxn][maxn],ll a[maxn]){
    ll temp[maxn]={0};
    for(int i=1;i<=p;i++) for(int j=1;j<=p;j++) temp[i]+=b[i][j]*a[j];
    memcpy(a,temp,sizeof(temp));
}
void mulself(ll a[maxn][maxn],ll b[maxn][maxn]){
    ll temp[maxn][maxn]={0};
    //if 判断是稀疏矩阵的优化，注意循环的顺序 
    for(int i=1;i<=p;i++) for(int k=1;k<=p;k++) if(a[i][k]) for(int j=1;j<=p;j++) temp[i][j]+=a[i][k]*b[k][j];
    memcpy(a,temp,sizeof(temp));
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Training little cats.in","r",stdin);
    while(cin>>n>>m>>k){
        if(!n&&!m&&!k) break;
        p=n+1; //p is the size of matrix
        pre();
        char ch;
        while(k--){
            getchar(); //enter
            cin>>ch;
            int pos,p1,p2;
            if(ch=='g'){ //get
                cin>>pos;
                e[pos][p]++;
            }
            if(ch=='e'){ //eat
                cin>>pos;
                for(int i=1;i<=p;i++) e[pos][i]=0;
            }
            if(ch=='s'){ //swap
                cin>>p1>>p2;
                for(int i=1;i<=p;i++) swap(e[p1][i],e[p2][i]);
            }
        }
        /*
        for(int i=1;i<=p;i++){
            for(int j=1;j<=p;j++){
                cout<<e[i][j]<<" ";
            }
            cout<<endl;
        }
        */
        while(m){
            if(m&1) mul(e,f);
            mulself(e,e);
            m>>=1;
        }
        for(int i=1;i<=n;i++) cout<<f[i]<<" ";
        cout<<endl;
    }
    return 0;
}

数据结构与DP

POJ 3171: Cleaning Shifts
算法竞赛进阶指南上的题目，也是挑战程序设计竞赛上面的题目。
$d[i]$ 表示覆盖 $\left [M,i\right ]$ 的最小代价。
先按照右端点升序排序，顺序考虑每个区间。
初值： $d[m-1]=0$ ，其余为INF
目标： $max\left \{ d[x]\right \}$ ，其中 $x\geq b_{i}$
转移方程： $d[b_{i}]=min\left \{ d[x]\right \}+S_{i}$ ，其中 $a_{i}-1\leq x\leq b_{i}$
ps：按照左端点升序排序来做也可行，目前原因未知。
代码如下

/*
算法竞赛进阶指南上的题目，也是挑战程序设计竞赛上面的题目。
d[i]表示覆盖[M,i]的最小代价。
先按照右端点升序排序，顺序考虑每个区间。
初值：d[m-1]=0，其余为INF 
目标：max{d[x]}，其中x>=b_{i}
转移方程：d[b_{i}]=min{d[x]}+S_{i}，其中a_{i}-1<=x<=b_{i} 
ps：按照左端点升序排序来做也可行，目前原因未知。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxL=86399+5;
const int INF=0x3f3f3f3f;
struct node {
    int x,y,s;
    bool operator<(const node &h)const {
        return (y<h.y)||(y==h.y&&x==h.x);
    }
} seq[maxn];
struct SegmentTree{
    int l,r,dat;
}tr[maxL<<2];
int n,m,e,ans=0;
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r){
        tr[rt].dat=INF;
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
void change(int rt,int pos,int v){
    if(tr[rt].l==tr[rt].r){
        tr[rt].dat=min(v,tr[rt].dat);
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(pos<=mid) change(rt<<1,pos,v);
    else change(rt<<1|1,pos,v);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
int ask(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
    int mid=tr[rt].l+tr[rt].r>>1;
    int val=INF;
    if(mid>=l) val=min(val,ask(rt<<1,l,r));
    if(mid<r) val=min(val,ask(rt<<1|1,l,r));
    return val;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Cleaning Shifts.in","r",stdin);
    cin>>n>>m>>e;
    for(int i=1; i<=n; i++) cin>>seq[i].x>>seq[i].y>>seq[i].s;
    sort(seq+1,seq+n+1);
    build(1,m-1,e); //这边只需要建立到e就可以了 因为如果change(1,seq[i].y,val+seq[i].s)中seq[i].y>e，会更新到e上，也算做合法 
    change(1,m-1,0);//f[m-1]=0
    for(int i=1;i<=n;i++){
        if(seq[i].y<m) continue;
        int val=ask(1,seq[i].x-1,seq[i].y);
        change(1,seq[i].y,val+seq[i].s);
    }
    int ans=INF;
    for(int i=1;i<=n;i++){
        if(seq[i].y>=e) ans=min(ans,ask(1,e,seq[i].y));
    }
    ans==INF?cout<<-1:cout<<ans;
    return 0;
}

动态规划（二）

状态压缩DP

矩阵的幂

数据结构与DP

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读