P1034 （C++代码）

解题思路:





注意事项:





参考代码:

普及组水题，适合dp练习：

1.

1.子任务 第i时刻尼克是否有任务可选 如果有，选哪个歇的时间更长
2.定义状态
在前i时刻尼克最多歇多久（最少工作多久）？
3.状态转移
本题要倒着推 及从大的时间往小的时间转移 因为 如果正着 在i的时候 显然还没转移 i+t
考虑如果 i时刻没有任务 则 从i+1秒 到第 i 秒可以歇着 就爽歪歪。
如果有任务 就 从这几个任务中 选择一个（根据程序选择轻松地，就美滋滋！）
及 dp【i】=dp【i+1】+1；
或 if t【j】。s==i
dp【i】=max(dp【i+t【j】。e】，dp【i】)；
具体看代码吧！
对了在解释一个问题 sort对于这题而言 如果你要 每次花j的复杂度扫下的话 拍不排序无所谓 ，但是排序后 你可以根据时间的单调性优化，
及每次并不用扫完 就可以用特判结束
不排序 复杂度（确界） nk
排序 （上界）nk +(下界)klogk 上界 （k^2） （排序只讨论sort）


#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct  node
{    int s,e;
}t[10000];int dp[10000];int st[100009];int cmp(node a,node b)
{    
return a.s>b.s;
}
int n,m,k;int main(){cin>>n>>k;for(int i=1;i<=k;i++)
{    cin>>t[i].s>>t[i].e;
st[t[i].s ]++;
}
sort(t+1,t+1+n,cmp);
dp[n+1]=0;for(int i=n;i>=1;i--)
{    if(st[i]==0)
    {
        dp[i]=dp[i+1]+1;
    }    else
    {    for(int j=1;j<=k;j++)
    {    if(t[j].s==i)    
dp[i]=max(dp[i+t[j].e ],dp[i]);        
    }
     }
}cout<<dp[1]<<endl;    return 0;
}

2.
这题显然是一个线性动规，
那么肯定是第一时间想到设f[i]:1~i的最大空闲时间，
但是，想了一下之后发现，第i时刻的最大空闲时间是和后面i+选择任务的持续时间的时刻有关系的，
那么，正着找肯定是不行的，我们来试一下倒着搜,即设f[i]表示i~n的最大空闲时间，
经尝试，发现是完全可行的，可以列出动态转移方程如下
（本时刻无任务）f[i]=f[i+1]+1;//继承上一个时刻的最大空闲时间后+1
（本时刻有任务）f[i]=max(f[i],f[i+a[sum])//a[sum]表示在这个时刻的任务的持续时间，
找出选择哪一个本时刻任务使空闲时间最大化
那么既然是倒着搜，从后往前的任务对应的开始时间自然也要反过来，
从大到小排序（同时也是为了把相同开始时间的任务放到一起）,
当然在进行状态刷新的时候别忘了拿sum不断计一下已经到哪一个任务了
那么。。喜闻乐见的，上代码。。。。
#include<iostream>  
#include<algorithm>  
using namespace std;  
long int n,k,sum[10001],num=1,f[10001];  
struct ren//结构体，一起排序 ，从大到小   {  
    long int ks,js;  
};  
ren z[10001];  
int cmp(ren a,ren b)  {  
    return a.ks>b.ks;  
}  
int main()  {  
    long int i,j;   
    cin>>n>>k;  
    for(i=1;i<=k;i++)  
    {  
    cin>>z[i].ks>>z[i].js;    
    sum[z[i].ks]++;  
    }  
    sort(z+1,z+k+1,cmp);  
    for(i=n;i>=1;i--)//倒着搜   
    {  
        if(sum[i]==0)  
        f[i]=f[i+1]+1;  
        else for(j=1;j<=sum[i];j++)  
        {  
            if(f[i+z[num].js]>f[i])  
            f[i]=f[i+z[num].js];  
            num++;//当前已扫过的任务数   
        }  
    }  
    cout<<f[1]<<endl;  
}  

3.这是献给Java同志们的：
题意要求.在某个时间上.niko有任务必须做.有多个任务选择任意1个.
问从开始到结束的最大空闲的时间.
首先当然要按起始时间排序..
之后呢.我们知道.空闲时间是从2个任务的中间时间省下来的..
究竟有没有这段空闲时间.?
如果有的话,说明在这中间1定没有其它任务了.
不然niko会优先做这个"其它的任务.".
不管这个任务做的究竟有多快.这段空闲时间1定被破坏了.
空闲时间虽然不完整.但是如果仍然存在.可以通过这个"其它的任务."来转移.
所以只要关注离这个任务开始时间最近的任务就行了..
那么设f[i]f[i]表示到第i个任务开始时.最大的空闲时间.
转移方程:f[i] = max(f[j]+p[i]-t[j]),(1 <= j<= i-1)f[i]=max(f[j]+p[i]−t[j]),(1<=j<=i−1).
p[i]p[i],t[i]t[i]表示任务ii的起始时间与结束时间.
其中ii要满足.p[i] = min(p[k],(1 <= k <= n,p[k] >= t[j]))p[i]=min(p[k],(1<=k<=n,p[k]>=t[j]))转移才成立.
看起来麻烦.?
伪代码.
for (int i = 1; i <= n; i++)    for (int j = 1; j <= i-1; j++)        if (p[i] >= t[j] && p[i] <= b[j]){
            f[i] = max(f[i],f[j]+p[i]-t[j]);
            b[j] = p[i];
        }
用b[j]b[j]记录下距离t[j]t[j]的最小值.
可行性很容易探究.-
最后把头尾2个当作工作加进去.输出f[n]f[n]就可以了..
最坏时间复杂度O(\frac{n^2}{2})O(2n2).空间O(4n)O(4n).还是能过的..
Diu代码..


program P1280; 
var
  b,f,x,y,z:array[0..10001] of longint;
  i,j,k,p,n:longint; function hahamax(x,y:longint):longint;   //最大值比较..(math.)
  begin
   if x>y then exit(x)          else exit(y);  end; procedure hahasort(l,r:longint);         //快速排序..
  var
   o,p,m,t:longint;  begin
   o:=l;
   p:=r;
   m:=x[(o+p) div 2];   repeat
    while x[o]<m do inc(o);    while x[p]>m do dec(p);    if o<=p then
     begin
      t:=x[o];
      x[o]:=x[p];
      x[p]:=t;
      t:=y[o];
      y[o]:=y[p];
      y[p]:=t;
      inc(o);
      dec(p);     end;   until o>p;   if o<r then hahasort(o,r);   if l<p then hahasort(l,p);  end; begin
  readln(n,k);  for i:=1 to k do
   begin
    readln(x[i],y[i]);                     //x,y就是上面的p,t.
    inc(y[i],x[i]);                        //做类似开区间处理..
   end;
  x[0]:=1;
  y[0]:=1; // fillchar(z,sizeof(z),0);               //调试用.-
  inc(k);
  x[k]:=n+1;                               //由于是开区间..
  y[k]:=n+1;                               //结束变成n+1..
  hahasort(1,k-1);  for i:=0 to k do
   begin
    b[i]:=1008208820;                      //初始化b[i]最大.
    f[i]:=-1008208820;                     //说明任务还不能做.
   end;
  f[0]:=0;                                 //working.
  for i:=0 to k do
   for j:=0 to i-1 do
    if (b[j]>=x[i]) and (x[i]>=y[j]) then
     begin
      f[i]:=hahamax(f[i],f[j]+x[i]-y[j]);  //能转移的转移.
      b[j]:=x[i];                          //找到最近的工作.
     end;                                  //可能有多个.
  writeln(f[k]); end.
  
 点赞最重要！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！