【题解】P1874 快速求和 二维背包

· · 题解

发一篇类似于背包的二维DP吧

首先设状态：

我们设 f [ i ][ j ] 表示 前 i位数字 组成 j 的最少加法次数

所以，类似于背包的转移方式，我们可以得到如下方程：

f [ i ] [ j ] = min { f [ i - k ] [ j - s [ i - k + 1 ] [ i ] ] + 1 , f [ i ] [ j ] } ;

即第二维类比于背包中的体积，

其中，s [ ] [ ] 数组是预处理出来的“原数” ， 即不添加号时的“非一位数”多位数 ， 由于数据中 n <= 100000 , 所以预处理出6位就足够了，但是要防备 像“03”的情况，所以再多开几位就好了……………… 惨痛的教训，我调了好几遍

方程出来后，然后是初始化 ： 因为求的是 min 值 ，所以全部初始化为极大值， 但是要切记 f [ 0 ] [ 0 ] = 0 , 否则无法完成转移

简洁的 DP 清晰的思路 代码如下 ：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define ll unsigned long long 
#define E 100007
using namespace std ;
string sr ; 
ll a[E] , s[43][43] , f[43][E] ; // 前 i 位数字 组成 j 的最少加法次数   f[i][j] = min { f[i-k][j-s[i-k+1][i]] + 1 , f[i][j] } ;  
int main(){
    cin >> sr ;
    ll len = sr.length() ; 
    for(ll i =  0 ; i < len ; i ++) a[i + 1] = sr[i] - '0' ; 
    for(ll i = 1 ; i <= len ; i ++)
    {
        s[i][i] = a[i] ; 
        for(ll j = i ; j - i <= 11 && j <= len ; j ++)
            s[i][j] = s[i][j-1] * 10 + a[j] ;
    }
    ll n ; cin >> n ;
    for(ll i = 0 ; i <= len + 1 ; i ++) for(ll j = 0 ; j <= n + 1 ; j ++) f[i][j] = 0x7fffffff ;  f[0][0] = 0 ;
    for(ll i = 1 ; i <= len ; i ++)
        for(ll k = 1 ; k <= 11 && i + k <= len + 3 ; k ++)
            if(i >= k)
                for(ll j = s[i-k+1][i] ; j <= n ; j ++)
                    f[i][j] = min(f[i-k][j-s[i-k+1][i]] + 1 , f[i][j])  ;
    if(n == 0) cout << 0 << endl ;
    else if(f[len][n] > len ) cout << -1 << endl ;      
    else cout << f[len][n] - 1 << endl ; 
    return -0 ; 
}

@作者troubler