题意概括

线性资源分配的问题，因为空闲的时间大小看后面的时间（反正感觉这个就是个套路）所以从后往前DP。

转移方程

如果当前时刻没有工作

f[i]=f[i+1]+1

如果当前时刻有工作

f[i]=max(f[i],f[i+时间段])

完整代码

#include <bits/stdc++.h>

using namespace std;

map<int,int> f,sum;

int p;

struct node

{

  int ks,js;

}num[10005];

bool cmp(node a,node b)

{

  return a.ks>b.ks;

}

int main()

{

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

  int n,k;

  cin>>n>>k;

  for(int i=0;i<k;i++)

  cin>>num[i].ks>>num[i].js,sum[num[i].ks]++;

  sort(num,num+k,cmp);

  for(int i=n;i;i--)

  {

    if(!sum[i])

    f[i]=f[i+1]+1;

    else for(int j=0;j<sum[i];j++)

    f[i]=max(f[i],f[i+num[p++].js]);

  }

  cout<<f[1];

}

巴特西

洛谷 P1280 尼克的任务 (线性DP)

题意概括

线性资源分配的问题，因为空闲的时间大小看后面的时间（反正感觉这个就是个套路）所以从后往前DP。

转移方程

如果当前时刻没有工作

f[i]=f[i+1]+1

如果当前时刻有工作

f[i]=max(f[i],f[i+时间段])

完整代码

最新文章

热门文章