digitDP

<div class="post_brief"><p> 题目名字好长。</p>   当年在考场上只会分块打表的题。   前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。   于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。   考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久）   然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。   然后还是没有原版跑得快。OTL。   #define PROC "shop" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 53; const int maxm = 509; const int mb = 253; dint l, r; int n, m, bs, a[maxn];...