挑选（pick）

1s/128MB

【题目背景】

NOIP2017 马上就要到了，丁爷爷想要从他的小朋友里挑选出一些厉害的来参加NOIP。

【题目描述】

丁爷爷共有 n 个小朋友，按编号 1 . . . n 从左到右排成一行。每个小朋友都有一个实力值，第 i 个小朋友的实力值为 wi。

丁爷爷作为一名爷爷，自然可以随意地挑选小朋友。但是如果他挑选的小朋友太靠近，就免不了给人一种内定、钦点的感觉了。他并不想这么做，于是他制定出了一个方案。

他给每个小朋友设置了一个气场值 ci，当丁爷爷挑选出 i 号小朋友参加 NOIP 后，他会把它右边的ci个小朋友（不包被挑选的小朋友本身）都自动淘汰。这些被淘汰的小朋友加上被丁爷爷挑选出的小朋友立即被移出队伍。接着，丁爷爷就可以继续他的挑选工作。需要注意的是，如果此时右边的小朋友个数不足ci，那么丁爷爷是不能进行这次挑选的。

作为丁爷爷的粉丝，你和 Yazid 都对丁爷爷的挑选工作很感兴趣。

你想知道丁爷爷小朋友们最高的实力值总和，而 Yazid则对挑选小朋友的本质不同的方案数很感兴趣。（两种挑选方案本质相同，当且仅当两种方案最终挑选出的小朋友完全一致。）

众所周知，Yazid 是一名辣鸡蒟蒻，于是你就需要同时求解这两个问题。由于方案数可能很大，所以对于 Yazid 的问题，你只需要回答对 998244353 取模的结果即可。

【输入格式】

从文件 pick.in 中读入数据。

第一行一个正整数 n，表示小朋友的数目。

接下来一行 n 个用空格隔开的非负整数 w1 . . . wn，依次描述 1 号小朋友至n号小朋友的实力值。

接下来一行 n 个用空格隔开的非负整数 c1 . . . cn，依次描述 1 号小朋友至n号小朋友的气场值。

【输出格式】

输出到文件 pick.out 中。

输出一行 2 个用空格隔开的整数，第一个整数表示挑选出的小朋友实力值总和的最大值，第二个整数表示本质不同的挑选方案数对 998244353 取模的结果。

【样例 1 输入】

7 2 3

2 0 0

【样例 1 输出】

7 5

【样例 2 输入】

27 68 75 76 75 75 68 40 33 62 58 88 4 75 766 84 52

1 2 3 3 2 4 1 2 3 3 5 1 3 1 1 3 2 1

【样例 2 输出】

490 3348

【样例 3】

见选手目录下的 pick/pick3.in 与 pick/pick3.ans。

【提示】

样例 1 解释：你可以挑选出 {}, {1}, {2},{3},{2, 3} 这些小朋友的子集，因此方案数为

5。其中，{1} 这个子集的小朋友实力值总和最大，总和为 7（只有 1 号小朋友）。

【子任务】

对于10% 的数据，保证 n ≤ 9。对于 30% 的数据，保证 n ≤ 18。对于 60% 的数据，保证 n ≤ 200。

对于另外20% 的数据，保证所有的 wi= 1，保证所有的 ci= 1。对于 95% 的数据，保证n≤ 3, 000。

对于 100% 的数据，保证 n ≤ 5, 000，wi ≤ 10^7，ci <n。

由这个题意似乎可以往一种常见的dp去想那就是---括号序列！

这里我们显然可以转化成若第i个填左括号，那么就要有ci个右括号来与之匹配。

那不就非常简单了吗？！

dp[i][j]表示前i个小朋友中左括号与右括号的差为j的最大实力值。

则dp[i][j]=max{dp[i-1]j+1,dp[i-1][j-c[i]]+wi}

if j==0 dp[i][j]=max{dp[i][j],dp[i-1][j]}可以不取。

辣么最后的结果就是dp[n][0]啦~

初值dp[0][0]=0就ok啦。

g[i][j]表示前i个小朋友中左括号与右括号的差为j的方案总数。

也是一样的道理，将max改成累加即可。

这道题的变形有点考思路，但变形好之后就很基本了qwq下次要记住啊...

code

#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

const int mod = 998244353;

const int MAXN = 5005;

inline ll read() {

    ll k = 0, f = 1;

    char ch = getchar();

    while (ch < '0' || ch > '9') {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (ch >= '0' && ch <= '9') {

        k = (k << 1) + (k << 3) + (ch & 15);

        ch = getchar();

    }

    if (f == -1) k = ~k + 1;

    return k;

}

inline void write(ll x) {

    if (x < 0)

        x = -x, putchar('-');

    if (x > 9)

        write(x / 10);

    putchar(x % 10 + '0');

}

int n;

int now;

ll w[MAXN],c[MAXN];

ll dp[2][MAXN],g[2][MAXN];

int main(){

	freopen("pick.in","r",stdin);

	freopen("pick.out","w",stdout);

	//n = read();

	scanf("%d",&n);

	for (int i = 1 ; i <= n ; i++){

		//w[i] = read();

		scanf("%d",&w[i]);

	}

	for (int i = 1 ; i <= n ; i++){

		//c[i] = read();

		scanf("%d",&c[i]);

	}	

	g[0][0] = 1;

	for (int i = 1 ; i <= n ; i++){

		now = 1 - now;

		for (int j = 0 ; j <= n ; j++){

			if (j == 0){

				dp[now][j] = max(dp[1 - now][j],dp[1 - now][j + 1]);

				if(j >= c[i]) dp[now][j] = max(dp[now][j],dp[1 - now][j - c[i]]+  w[i]);

				g[now][j] = (g[1 - now][j] + g[1 - now][j + 1]) % mod;

				if(j >= c[i]) g[now][j] = (g[now][j] + g[1 - now][j - c[i]]) % mod;

			}

			else{

				dp[now][j] = dp[1 - now][j + 1];

				if(j >= c[i]) dp[now][j] = max(dp[now][j],dp[1 - now][j - c[i]] + w[i]);

				g[now][j] = g[1 - now][j + 1];

				if(j >= c[i]) g[now][j] = (g[now][j] + g[1 - now][j - c[i]]) % mod;

			}

		}

	}

	//write(dp[now][0]),putchar(32),write(g[now][0]);

	printf("%lld %lld",dp[now][0],g[now][0]);

	return 0;

}

巴特西

挑选(pick)

挑选（pick）

code

最新文章

热门文章