题意:有N节装有一定人数的车厢,现在想用3个可以来M节车厢的火车头,求3个火车头最多可以带走多少人
思路:1、先预处理出每M节车厢的总人数,出入val数组中
2、f[0][i]=maxm[0]+val[i];
f[1][i]=maxm[1]+val[i];
maxm[0]=MAX(val[i-m+1],maxm[0]);
maxm[1]=MAX(f[0][i-m+1],maxm[1]);
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX(a,b) (a>b?a:b)
const int M(51000);
int a[M],val[M],f[2][M];
void dp(int n,int m)
{
int i,maxm[3];
//memset(f,0,sizeof(f));
maxm[0]=val[0];
maxm[1]=0;
for(i=m;i<n;i++)
{
f[0][i]=maxm[0]+val[i];
f[1][i]=maxm[1]+val[i];
maxm[0]=MAX(val[i-m+1],maxm[0]);
maxm[1]=MAX(f[0][i-m+1],maxm[1]);
//f[i]=val[i]+maxm;
//maxm=MAX(f[i-m+1],maxm);
}
maxm[0]=0;
for(i=0;i<n;i++)
maxm[0]=MAX(f[1][i],maxm[0]);
printf("%d\n",maxm[0]);
}
int main()
{
int t,i,j,k,n,m,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
sum=0;
for(i=0,j=0;i<n;i++)
{
sum+=a[i];
if(i>=m-1)
{
val[j++]=sum;
sum-=a[i-m+1];
}
}
dp(j,m);
}
}
分享到:
相关推荐
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1747400
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1746750
北大POJ1942-Paths on a Grid 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
poj分类poj分类poj分类poj分类
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
2遍dp poj_3613解题报告 poj_3613解题报告
北大POJ1159-Palindrome 解题报告+AC代码