poj 1976 A Mini Locomotive(0/1背包)

点击打开链接poj 1976

思路: 0/1背包
分析:
1 题目给定n个数，要求三段连续的m个数之和最大
2 假设n个数是num[1],num[2],num[3]......num[n]，那么m个连续的数可能有n-m+1种可能即num[1]+num[2]...+num[k] , num[2]+num[3]...+num[k]......

3 我们令v[1] = num[1]+num[2]...+num[k] , v[2] = num[2]+num[3]...+num[k].那么总的有n-m+1个物品每个体积为1，那么我们令dp[i][j]表示的是前i个物品放入容量为j的背包的最大值，背包的总容量为3.
那么dp[i][j]的转移方程很好写出
i >= m , dp[i][j] = max(dp[i-1][j] , dp[i-m][j-1]+v[i]);
i < m , dp[i][j] = max(dp[i-1][j] , v[i]);
怎么理解这个转移方程呢？原因就是因为这边由于每个物品是m个连续的数，所以说我们在取了第i个物品的时候很明显前面的m个物品不能取（因为数字是不能重复的）。当i < m的时候，很明显就是要么不取第i个，如果要取就是直接的v[i]。

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

int n , m , num[MAXN];
int v[MAXN] , dp[MAXN][4]; 

int solve(){
    int sum;
    for(int i = 1 ; i <= n-m+1 ; i++){
        sum = 0;
        for(int j = i ; j <= i+m-1 ; j++)
            sum += num[j];
        v[i] = sum;
    }
    memset(dp , 0 , sizeof(dp));
    for(int i = 1 ; i <= n-m+1 ; i++){
        for(int j = 3 ; j >= 1 ; j--){
            if(i >= m)
                dp[i][j] = max(dp[i-1][j] , dp[i-m][j-1]+v[i]);
            else
                dp[i][j] = max(dp[i-1][j] , v[i]);
        }
    }
    return dp[n-m+1][3];
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
         scanf("%d" , &n);
         for(int i = 1 ; i <= n ; i++)
             scanf("%d" , &num[i]);
         scanf("%d" , &m);
         printf("%d\n" , solve());
    }
    return 0;
}