动态规划（二）
2019-07-27 本文已影响0人
云中翻月
状态压缩DP
POJ 2441: Arrange the Bulls
表示前i头cow，目前畜栏使用情况为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数组表示可行的二进制数集合。
表示前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。
表示目前覆盖状态为i的最小面积和。（注意重合的面积，重合几次就计算几次）
初值：，其他为INF
目标：
转移方程：
其中
表示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
算法竞赛进阶指南上的题目，也是挑战程序设计竞赛上面的题目。
表示覆盖
的最小代价。
先按照右端点升序排序，顺序考虑每个区间。
初值：，其余为INF
目标：，其中
转移方程：，其中
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;
}
