挑选

挑选（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 输入】

3

7 2 3

2 0 0

【样例 1 输出】

7 5

【样例 2 输入】

18

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≤ 107，ci<n。

题解：这是一道Dp题。我们将选第i个数当为加c[i]个左括号，不选一个当为加1个右括号。用dp1[i][j]表示选到第i个数left-right=j时的最优方案。当j=0时dp1[i,j]:=max(dp1[i-1,j],dp1[i-1,j+1],dp1[i-1,j-c[i]]+w[i])。当j>0时dp1[i,j]:=max(dp1[i-1,j+1],dp1[i-1,j-c[i]]+w[i]);用dp[i][j]表示选到第i个数left-right=j时的方案数。当j=0时dp[i,j]:=dp[i-1,j]+dp[i-1,j+1]+dp[i-1,j-c[i]])。当j>0时dp[i,j]:=dp[i-1,j+1]+dp1[i-1,j-c[i]]。由于空间原因我们可以再加滚动进行优化。

Code：

var
  n,i,j,now:longint;
  w,c:array[0..5005] of longint;
  dp,dp1:array[0..1,0..5005] of int64;
function max(a,b:int64):int64;
begin
  if a>b then exit(a) else exit(b);
end;
begin
  assign(input,'pick.in');reset(input);
  assign(output,'pick.out');rewrite(output);
  readln(n);
  for i:=1 to n do read(w[i]);
  for i:=1 to n do read(c[i]);
  now:=0;
  for i:=1 to n do
  begin
    now:=1-now;
    for j:=0 to n do
    begin
      if j=0 then
      begin
        dp1[now,j]:=max(dp1[1-now,j],dp1[1-now,j+1]);
        if j>=c[i] then dp1[now,j]:=max(dp1[now,j],dp1[1-now,j-c[i]]+w[i]);
      end else
      begin
        dp1[now,j]:=dp1[1-now,j+1];
        if j>=c[i] then dp1[now,j]:=max(dp1[now,j],dp1[1-now,j-c[i]]+w[i]);
      end;
    end;
  end;
  write(dp1[now,0],' ');
  dp[0,0]:=1;
  now:=0;
  for i:=1 to n do
  begin
    now:=1-now;
    for j:=0 to n do
    begin
      if j=0 then
      begin
        dp[now,j]:=(dp[1-now,j]+dp[1-now,j+1]) mod 998244353;
        if j>=c[i] then dp[now,j]:=(dp[now,j]+dp[1-now,j-c[i]]) mod 998244353;
      end else
      begin
        dp[now,j]:=dp[1-now,j+1];
        if j>=c[i] then dp[now,j]:=(dp[now,j]+dp[1-now,j-c[i]]) mod 998244353;
      end;
    end;
  end;
  writeln(dp[now,0]);
  close(input);close(output);
end.