本文共 1515 字,大约阅读时间需要 5 分钟。
东东每个学期都会去寝室接受扫楼的任务,并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+…+a[j]个人 这让宿管阿姨非常开心,并且让东东扫楼m次,每一次数第i到第j个宿舍sum(i,j) 问题是要找到sum(i1, j1) + … + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。 注:1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)
Input
输入m,输入n。后面跟着输入n个ai Output 输出最大和 Sample Input 1 3 1 2 3 2 6 -1 4 -2 3 -2 3 Sample Output 6 8 Hint 数据量很大,需要scanf读入和dp处理。题目解析
刚看到这个题的时候,有点懵逼。然后又读了一遍,understand。dp问题问: 输入一个n,表示区间长度为n,现在要选取m个区间,使得这m个区间里的数加起来和最大。 m个区间中,每个区间无相交部分,比如上述输样例第二个 2 6 -1 4 -2 3 -2 3 a[1] a[2] a[3] a[4] a[5] a[6] -1 4 -2 3 -2 3 要选2个区间,第一次选择(2,2),sum(2,2)=4 第二次选择(4,6),sum(4,6)=4 所以最大为8.那么怎么做涅? 就是选与不选,变大与变小,具体过程见代码
注意:把ans设置为long long长整型,因为n最大1e6,a[i]最大32767所以ans最大32767*1e6,超过了整型范围,而且事实证明我把ans由int 改为long long后,结果就由wa变成ac了。为了避免麻烦,我就直接用C语言写了
Codes
#includeconst int maxn=1e6+10;int m,n;long long ans;int dp[maxn],a[maxn],f[maxn];int max(int x,int y){ //标准C语言里面是木有max函数的,所以自己写 return x>y? x:y;}void ini(){ //初始化 for(int i=0;i<=n;i++){ dp[i]=0; f[i]=0; } ans=-1e10;//因为人数可为负,不妨把ans写小点}int main(){ while(scanf("%d%d",&m,&n)!=EOF){ ini(); for(int i=1;i<=n;i++)//输入 scanf("%d",&a[i]); for(int j=1;j<=m;j++){ //选区间数 for(int i=j;i<=n;i++){ //dp选出区间内最大和 dp[i]=max(dp[i-1]+a[i],f[i-1]+a[i]); if(i==j||i==j+1) f[i-1]=dp[i-1];//更新完当前区间 else f[i-1]=max(f[i-2],dp[i-1]); } } for(int i=m;i<=n;i++)//选出最大值 ans=max(ans,dp[i]); printf("%lld\n",ans); } return 0;}
转载地址:http://mdwzi.baihongyu.com/