生活随笔
收集整理的這篇文章主要介紹了
Gym - 100543L
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Gym - 100543L
https://vjudge.net/problem/153854/origin
區間dp，要從區間長度為1開始dp
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<
set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 1010
#define For(i,a,b) for(long long i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
using namespace std;
long long T;
long long n,m;
struct node{long long l;long long r;long long w;
}a[N];
long long b[N],id,Max;
long long f[N][N];
void in(
long long &
x){long long y=
1;char c=g();x=
0;while(c<
'0'||c>
'9'){if(c==
'-')y=-
1;c=
g();}while(c<=
'9'&&c>=
'0'){x=(x<<
1)+(x<<
3)+c-
'0';c=
g();}x*=
y;
}
void o(
long long x){if(x<
0){p('-');x=-
x;}if(x>
9)o(x/
10);p(x%
10+
'0');
}void clear(){m=
0;//memset(f,0,sizeof(f));
}int main(){in(T);while(T--
){clear();in(n);For(i,1,n){in(a[i].l);
in(a[i].r);
in(a[i].w);b[++m]=
a[i].l;b[++m]=
a[i].r;}sort(b+
1,b+m+
1);m=unique(b+
1,b+m+
1)-b-
1;For(i,1,n){a[i].l=lower_bound(b+
1,b+m+
1,a[i].l)-
b;a[i].r=lower_bound(b+
1,b+m+
1,a[i].r)-
b;}For(len,1,m)For(l,1,m-len+
1){int r=l+len-
1;id=
0;For(i,1,n)if(a[i].l>=l&&a[i].r<=
r)if(id==
0||a[i].w>
a[id].w)id=
i; if(id==
0){f[l][r]=
0;continue;}f[l][r]=
inf;For(i,a[id].l,a[id].r)f[l][r]=min(f[l][r],f[l][i-
1]+f[i+
1][r]+
a[id].w);}o(f[1][m]);p(
'\n');}return 0;
}
轉載于:https://www.cnblogs.com/war1111/p/11219063.html
總結
以上是生活随笔為你收集整理的Gym - 100543L的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
