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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。