被鸽了的文件清除

NC53778. 被鸽了的文件清除

描述

众所周知，你整天浏览一些网站有时候因为你手贱，有些奇奇怪怪的东西不知不觉开始下载，而你一般会立刻点掉他们，但是却因为你很懒没有把残留文件删掉

众所周知，时间久了，因为没有删掉残留文件你手机的内存会越来越少。

现在你的手机内存已经枯竭，你要去外太空找新能源(走错了)

现在你要开始清除残留的n个文件。

清除的方式有2种:

1.手动删除;
2.软件删除

但是你很懒，你今天至多手动删除x个文件。

手动删除必须满足上一次是软件删除，而软件删除没有要求。

第i个文件，手动删除扩充 $a_i$ 单位的内存，软件删除扩充 $b_i$ 单位的内存

现在你想知道你今天最多扩出多少内存来

输入描述

一行一个整数n,x 表示一共有n个文件，至多手动删x个文件
接下来n行，每行两个整数a,b 表示手动删除扩充a单位的内存,软件删除扩充b单位的内存

输出描述

一行一个整数表示最多扩充多少内存

示例1

输入:

输出:

说明:

一次机会

如果手动删除1，答案是 1 + 1 + 2 + 3 = 7

如果手动删除2，答案是 1 + 2 + 2 + 3 = 8

如果手动删除3，答案是 1 + 1 + 3 + 3 = 8

如果手动删除4，答案是 1 + 1 + 2 + 4 = 8

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 184ms, 内存消耗: 1148K, 提交时间: 2020-03-26 14:54:33

#include<bits/stdc++.h>
using namespace std;

long long DP[2][1005][2]={0};
int n,x,a[100005],b[100005];
int main()
{
    int i,j;
    scanf("%d%d",&n,&x);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    for(i=1;i<=n;i++)
    {
    	DP[i&1][0][1]=DP[(i-1)&1][0][1]+b[i];
		for(j=1;j<=min(x,n);j++)
    	{
			if(i>1)DP[i&1][j][0]=DP[(i-1)&1][j-1][1]+a[i];
    		DP[i&1][j][1]=max(DP[(i-1)&1][j][1],DP[(i-1)&1][j][0])+b[i];
		}
	}
	printf("%lld\n",max(DP[n&1][x][0],DP[n&1][x][1]));
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 187ms, 内存消耗: 612K, 提交时间: 2019-09-29 10:55:40

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
int n,m,a,b;
LL dp[2][N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        for(int j=min(m,i);j>=0;j--)
        {
            dp[0][j]=max(dp[0][j],dp[1][j])+b;
            dp[1][j]=j?dp[0][j-1]+a:0;
        }
    }
    LL ans=0;
    for(int i=0;i<=min(n,m);i++)
        ans=max(ans,max(dp[0][i],dp[1][i]));
    cout<<ans<<endl;
    return 0;
}