洛谷p2904 River Crossing S

运用到了背包的思想
题目链接

大意

农夫想运$n$头牛过河，农夫每次自己过河需要$m$分钟，给定$n$个元素的数组$a$，表示多运$i$头牛则多需要$a[i]$的时间来划船

思路

把$dp[j]$当作运到第$j$头牛所花费的时间，容易得到转移方程：$dp[j]=max(dp[j],dp[j-i]+sum[i]$，$sum[i]$是一次运输$i$头牛花费的时间，循环就是了

ACcode

#include<bits/stdc++.h>

using namespace std;

const int M = 2e5 + 9;
int dp[M], sum[M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;cin >> n >> m;
    vector<int>a(n + 3);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        dp[i] = INT_MAX;
    }
    for (int i = 1;i <= n;i++)sum[i] += 2 * m;
    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j++) {
            dp[j] = min(dp[j], dp[j - i] + sum[i]);
        }
    }
    cout << dp[n] - m;
    return 0;
}