洛咕题解 P1280 尼克的任务[线性DP]

  • A+
所属分类:代码笔记 信息技术

题面

f[i]表示时间i~n内的最大休息时间(问什么设什么)

已知f[n+1]=0, 求f[1]

转移方程:(无任务时直接从下一秒+1转移过来, 有任务则只能从这个任务完成之后的时刻转移)

f[x]=f[x+1]+1 (x时刻无任务)

f[x]=max(f[x],f[x+task[j].t]) (x时刻有任务, 所有task[j].p==x)

明显要逆推, f[x]是从x时刻之后的状态转移来的

  1. #include<cstdio>
  2. #define re register
  3. #define in inline
  4. #define int long long
  5. inline int read()
  6. {
  7.     int s=0,b=1;
  8.     char ch;
  9.     do{
  10.         ch=getchar();
  11.         if(ch=='-') b=-1;
  12.     }while(ch<'0' || ch>'9');
  13.     while(ch>='0' && ch<='9')
  14.     {
  15.         s=s*10+ch-'0';
  16.         ch=getchar();
  17.     }
  18.     return b*s;
  19. }//快读是不可能出锅的
  20. int n,k;
  21. struct node{
  22.     int p,t;
  23. }task[11000];
  24. int f[11000],b[11000];
  25. int max(int x,int y)
  26. {
  27.     return x>y?x:y;
  28. }
  29. signed main()
  30. {
  31.     n=read();
  32.     k=read();
  33.     for(re int i=1;i<=k;++i)
  34.     {
  35.         task[i].p=read();
  36.         task[i].t=read();
  37.         ++b[task[i].p];
  38.     }
  39.     for(re int i=n;i>=1;--i)
  40.     {
  41.         if(!b[i]) f[i]=f[i+1]+1;
  42.         else
  43.         {
  44.             for(re int j=1;j<=k;++j)
  45.             {
  46.                 if(task[j].p==i)
  47.                     f[i]=max(f[i+task[j].t],f[i]);
  48.             }
  49.         }
  50.     }
  51.     printf("%lld\n",f[1]);
  52.     return 0;
  53. }
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: