板刷计划:ARC059

传送门:https://atcoder.jp/contests/arc059/tasks

让你将n个数变成一样。变一个数的代价是距离的平方.

方法一：由于数据范围比较小，暴力枚举最终相等点即可。

方法二：根据不等式的知识,显然将其变为平均值的代价最小。但是要求是整数，所以求离平均值最近的两个整数就好.

给你一个字符串，让你找出其中一段子串。使得其中最多的字符出现超过它长度的一半。SPJ。

思路:

要么XX,要么XAX. 容易证明这样的形式是最优的。

$给你N个物品。每个物品有一个价值x_i.选k次物品x_i的价值是 x_i^k$ . 现在你能选C个物品出来。得到的价值是每个物品的价值的累乘。令 $f(x_1,x_2,...x_n)$ 为所有分配方案的价值和。

求 $\sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} ... \sum_{x_i=A_i}^{B_i} f(x_1,x_2,...x_n) \ \ mod \ \ 1e9+7$

$数据范围: n,c,A_i,B_i<=400$

思路:

先考虑单纯求函数 $f$ .这里切记不要死板的套背包模板。先选几个数据带进去展开找找规律

自顶向下的考虑这个问题。当新增一个物品 $x_i$ 时.枚举物品选多少次有以下转移.

$dp[i][V] = \sum_{k=0}^V x_i^k * dp[i-1][V-k]$

利用前缀和优化有： $O(n^2)$

$dp[i][V] = dp[i][V-1] + x_i * dp[i-1][V]$

对于不同的 $x_i$ ,同时开多个temp数组一起转移，最后汇总(我也迷，讲不清).还好样例给的全，不然这题说不定还出不来.

https://atcoder.jp/contests/arc059/submissions/16989448

题目大意:

给你一个键盘,有三个键, 0 , 1 , del. 你要按下N次键盘。问你能够构造出字符串 S的方案数. |S| <= N.

核心思想：

首先一定要明确一点，才能动笔写这道题目:

方案数和这个字符串具体结构无关。只与这个字符串的长度有关.因为按下0或者1的概率(或者说代价)是一样的。我们只需要求出【按下n次键盘后得到长度为|S|的字符串的方案数】,最后再除掉 2^|S|.

这个容易用dp解决: $dp(i,j)代表按下i次键盘得到长度为j的字符串的方案数$

每个状态能够影响两个状态- 按下0,1转移到dp(i+1,j+1).按下del转移到dp(i+1,min(0,j-1)).。但是每个状态可能被很多状态影响。所以自然使用刷表法计数.

$dp(i+1,j+1)+= 2*dp(i,j)$

$dp(i+1,min(0,j - 1)) += dp(i,j)$

拓展：0,1拓展成小写字母一样可以。