本文共 1614 字，大约阅读时间需要 5 分钟。

题意

有一个奶牛，每次可以选择一个挤奶任务，完成任务之后需要休息R小时，现在一共有M个任务，问如何分配任务使得N小时内产奶量最大

AC

• dp[ i ] 表示做这个任务的最大产量
  （每个dp都要有一个确定的状态）
  dp[ i ] = max(dp[ i ], dp[ j ] + c[ i ])

using namespace std;int dp[1003];struct task{    int s, e, w;};bool cmp(const task &x, const task &y) {    return x.s < y.s;}int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int n, m, r;    cin >> n >> m >> r;    vector
   
     a(m);    for (int i = 0; i < m; ++i) {        cin >> a[i].s >> a[i].e >> a[i].w;    }    sort(a.begin(), a.end(), cmp);    int ans = -1;    for (int i = 0; i < m; ++i) {        dp[i] = a[i].w;        for (int j = i - 1; j >= 0; --j) {            if (a[j].e + r <= a[i].s) {                dp[i] = max(dp[i], dp[j] + a[i].w);            }        }        ans = max(ans, dp[i]);    }    cout << ans << endl;    return 0;}
   

• dp
  dp[ i ] 当前任务最大的情况,有选和不选当前任务两种情况
  dp[ i ] = max(dp[ i - 1], dp[ j ] + a[ i ])

using namespace std;int dp[1003];struct task{    int s, e, w;};bool cmp(const task &x, const task &y) {    return x.e < y.e;}int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int n, m, r;    cin >> n >> m >> r;    vector
   
     a(m);    for (int i = 0; i < m; ++i) {        cin >> a[i].s >> a[i].e >> a[i].w;    }    sort(a.begin(), a.end(), cmp);    dp[0] = a[0].w;    for (int i = 1; i < m; ++i) {        dp[i] = a[i].w;        for (int j = i - 1; j >= 0; --j) {            if (a[j].e + r <= a[i].s) {                dp[i] = max(dp[j] + a[i].w, dp[i]);                break;            }        }        dp[i] = max(dp[i - 1], dp[i]);    }    cout << dp[m - 1] << endl;    return 0;}
   

转载地址：http://bkprf.baihongyu.com/