題目

P1874 快速求和

算法標簽: 動態規劃, 線性$dp$

思路

求的是最少組成$n$的加法次數, 對于當前數字序列可以設計狀態表示$f[i][j]$表示考慮前$i$個字符, 并且和是$j$的所有方案中加法次數最小的方案, 那么就要考慮狀態轉移, 按照最后一步的思想, 可以將集合劃分為最后一個數字的長度, 也就是最后一個數字是什么, 算法時間復雜度$O(n\times len)$

代碼

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const LL INF = 5e18, N = 55, M = 1e5 + 40;string s;
LL w[N], nums[N][N], cnt;
LL sum, n, f[N][M];
bool vis;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> s >> sum;n = s.size();//去除前導0for (int i = 0; s[i]; ++i) {if (s[i] != '0') vis = true;if (vis) w[++cnt] = s[i] - '0';}if (cnt == 0) w[++cnt] = 0;//預處理兩個位置直接組成的數字大小for (int i = 1; i <= cnt; ++i) {nums[i][i] = w[i];for (int j = i; j - i <= 11 && j <= cnt; ++j) {nums[i][j] = nums[i][j - 1] * 10 + w[j];}}//初始化dpfor (int i = 0; i <= cnt + 1; ++i) {for (int j = 0; j <= sum + 1; ++j) f[i][j] = INF;}f[0][0] = 0;for (int i = 1; i <= cnt; ++i) {//枚舉最后一個數字的大小for (int k = 1; k <= 11; ++k) {if (i >= k) {LL curr = nums[i - k + 1][i];for (LL j = curr; j <= sum; ++j) {f[i][j] = min(f[i][j], f[i - k][j - curr] + 1);}}}}int ans;if (f[cnt][sum] > cnt) ans = -1;else ans = f[cnt][sum] - 1;cout << ans << "\n";return 0;
}