首页 > 其他分享 >Alibaba UVA - 1632

Alibaba UVA - 1632

时间:2023-04-13 22:58:05浏览次数:43  
标签:1632 min int Alibaba 耗时 UVA inf 珠宝 dis

一条直线的同一个方向上有 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

相关文章

  • uva 11082 A Plug for UNIX
     #include<iostream>#include<vector>#include<map>#include<queue>#include<cstring>usingnamespacestd;constintN=1e4+2,M=5e5;intn1,n2,n3,len;map<string,int>mp;map<int,int>A,B;constintin......
  • Calling Circles UVA - 247
    如果两个人相互打电话(直接或间接),则说他们在同一个电话圈里。例如,a打给b,b打给c,c打给d,d打给a,则这4个人在同一个圈里;如果e打给f但f不打给e,则不能推出e和f在同一个电话圈里。输入n(n≤25)个人的m次电话,找出所有电话圈。人名只包含字母,不超过25个字符,且不重复 对于一个有向图,Flo......
  • UVa 10049 Self-describing Sequence (自描述序列&二分递推)
    10049-Self-describingSequenceTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990SolomonGolomb's self­describingsequence  istheonlynon­decreas......
  • Shanghai 2006 / UVa 1382 Distant Galaxy (枚举&扫描&动态维护)
    1382-DistantGalaxyTimelimit:3.000seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4128YouareobservingadistantgalaxyusingatelescopeabovetheAstronomyTower,......
  • UVa 514 Rails (water ver.)
    514-RailsTimelimit:3.000seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=455ThereisafamousrailwaystationinPopPushCity.Countrythereisincrediblyhilly.Thest......
  • UVa 11044 Searching for Nessy (water ver.)
    11044-SearchingforNessyTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1985TheLochNessMonsterisamysteriousandunidentifiedanimalsaidtoinhabi......
  • UVa 846 Steps (数学)
    846-StepsTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=787Onestepsthroughintegerpointsofthestraightline.Thelengthofastepmustbenonnegat......
  • UVa 253 Cube painting (模拟)
    253-CubepaintingTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=189Wehaveamachineforpaintingcubes.Itissuppliedwiththreedifferentcolors:bl......
  • UVa 11498 Division of Nlogonia (water ver.)
    11498-DivisionofNlogoniaTimelimit:1.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2493TheProblemAftercenturiesofhostilitiesandskirmishesbetweenthefour......
  • UVa 11723 Numbering Roads (water ver.)
    11723-NumberingRoadsTimelimit:1.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2823Inmycountry,streetsdon’thavenames,eachofthemarejustgivenanumber......