当前位置: 首页 > 工具软件 > Locomotive > 使用案例 >

POJ - 1976 A Mini Locomotive(DP)

凌昕
2023-12-01

POJ - 1976 A Mini Locomotive

题意:

  • 给定n个数,要求三段连续的m个数之和最大

分析:

  • 为了求某个子段的和,我们通过前缀和预处理
  • 题目上给出 m < = n / 3 m<=n/3 m<=n/3 ,所以按照贪心的思想,为了和最大,每个区间一定是要m个长度的连续子段
  • d p [ i ] [ j ] dp[i][j] dp[i][j] 代表前 i i i 个数,用 j j j 个区间,最大值是多少。
  • 对于第 i i i 个数,如果当前这个区间选择要选择这个数,那么要把以 i i i 为最后一个数的连续m个数一起选择,所以状态转移方程是
  • d p [ i − m ] [ j − 1 ] + ( d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − m ] [ j − 1 ] + a [ i ] − a [ i − m ] ) a [ i ] − a [ i − m ] ) dp[i-m][j-1]+(dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m])a[i]-a[i-m]) dp[im][j1]+(dp[i][j]=max(dp[i1][j],dp[im][j1]+a[i]a[im])a[i]a[im])
#include<iostream>
#include<cstring>
using namespace std;

const int N = 50010;
int a[N],dp[N][5];

int main()
{
    int T;cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof dp);
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=2;i<=n;i++) a[i]+=a[i-1];
        int m;cin>>m;
        for(int i=m;i<=n;i++)
            for(int j=3;j>=1;j--)
                dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+a[i]-a[i-m]);
        cout<<dp[n][3]<<endl;
    }
    return 0;
}
 类似资料: