题目链接:传送门
题目思路:枚举w的排列,然后dp;求dp[i] ,要满足所有关于 j 的不等式 dp[i] >= len_max(v[i]<w[i]+w[i-1]+...+w[j]) + dp[j] ,len_max 指满足不等式的所有v[k]对应的l[k] 取max
因此,状态转移方程为:dp[i] = max( dp[i] , len_max(v[k]<w[i]+w[i-1]+...+w[j]) + dp[j] ) ,其中 len_max(v[k]<w[i]+w[i-1]+...+w[j]) + dp[j]可以理解成 求i,j的最小距离,i到j的重量为w[i]+w[i-1]+...+w[j],要使其满足j -> i 不会使某一座桥倒塌,那么就必须满足这个不等式。
#include<bits/stdc++.h> #pragma GCC optimize(2) using namespace std; std::mt19937 rnd(233); typedef long long LL; typedef pair<int,int> pii; typedef pair<LL,LL> pLL; #define pb push_back #define mk make_pair #define fi first #define se second #define ls (i<<1) #define rs (i<<1|1) #define mem(a,b) memset(a,b,sizeof(a)) const int N=1e6+5; const int inf=0x3f3f3f3f; const LL mod=1e9+7; LL read() { LL x=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return f*x; } pii a[N]; int l[N],w[N],b[N]; LL dp[10],sum[10]; int main() { int n=read(),m=read(),ma=0,mi=1e9; for(int i=1;i<=n;i++) w[i]=read(),ma=max(ma,w[i]); for(int i=1;i<=m;i++) { a[i].se=read(); a[i].fi=read(); mi=min(mi,a[i].fi); } if(mi<ma) return 0*printf("-1\n"); sort(a+1,a+m+1); for(int i=1;i<=m;i++) l[i]=max(a[i].se,l[i-1]); sort(w+1,w+n+1); LL ans=1e18; do { //for(int i=1;i<=n;i++) printf("%d%c",w[i],i==n?'\n':' '); mem(dp,0); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i]; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) { int tmp=sum[i]-sum[j-1]; int pos=lower_bound(a+1,a+m+1,mk(tmp,0))-a-1; //printf("%d\n",pos); dp[i]=max(dp[i],dp[j]+l[pos]); } ans=min(dp[n],ans); }while(next_permutation(w+1,w+n+1)); printf("%lld\n",ans); return 0; }View Code