在一条直线的同一个方向上有 nn 件珠宝,已知每件珠宝的位置,并且第 ii 件珠宝在 Ti时刻消失,
问将所有的珠宝收集起来最小耗时? 搜集不耗时,移动需要耗时
类似区间dp
f[i ][ j ] [2]
#pragma GCC optimize(2) #include <iostream> using namespace std; const int N=1e4+3; #define inf 1e9 int f[N][N][2],n,a[N],b[N]; int dis(int i,int j){ return a[j]-a[i]; } int main(){ std::ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int i,j; while(cin>>n){ for(i=1;i<=n;i++) for(j=1;j<=n;j++)f[i][j][0]=f[i][j][1]=inf; for(i=1;i<=n;i++) cin>>a[i]>>b[i],f[i][i][0]=f[i][i][1]=0; for(j=2;j<=n;j++) for(i=j-1;i>0;i--){ f[i][j][0]=min(f[i+1][j][0]+dis(i,i+1), f[i+1][j][1]+dis(i,j)); if(f[i][j][0]>=b[i]) f[i][j][0]=inf; f[i][j][1]=min(f[i][j-1][1]+dis(j-1,j), f[i][j-1][0]+dis(i,j)); if(f[i][j][1]>=b[j]) f[i][j][1]=inf; } int ans=min(f[1][n][0],f[1][n][1]); if(ans!=inf) cout<<ans<<endl; else cout<<"No solution\n"; } }
标签:1632,min,int,Alibaba,耗时,UVA,inf,珠宝,dis From: https://www.cnblogs.com/towboa/p/17316864.html