明確題意

等號(hào)左邊是由'+'和'?'組成的算式，其中處于某個(gè)整數(shù)(即便這個(gè)整數(shù)只有一位)首位的'?'可以填入1-9中的某個(gè)數(shù)字，其余'?'可以填入0-9中的某個(gè)數(shù)字。
SOURCE

這里未明確等號(hào)左邊有幾個(gè)整數(shù)（至少有一個(gè)）。讀題時(shí)我未能仔細(xì)理解這句話的含義，根據(jù)樣例誤認(rèn)為有且僅有兩個(gè)整數(shù)相加。另外，等號(hào)右邊的非負(fù)整數(shù)，題目雖未明確是否有前導(dǎo)零，可以認(rèn)為沒(méi)有（不應(yīng)該在這里糾結(jié)題意）。

做題的第一步是讀題，誠(chéng)哉斯言！

解法

數(shù)位DP。

將等號(hào)右邊的非負(fù)整數(shù)的數(shù)位，按從低位到高位的順序從1開(kāi)始編號(hào)。

$dp[i][j]$：滿足前 $i$ 位且對(duì)第 $i+1$ 位的進(jìn)位是 $j$ 的方案數(shù)

$n$ 個(gè)正整數(shù)相加， 每一位向前一位的進(jìn)位都小于 $n$

狀態(tài)轉(zhuǎn)移便轉(zhuǎn)化成了組合計(jì)數(shù)問(wèn)題。

將 $n$ 個(gè)相同的球放進(jìn) $m$ 個(gè)不同的盒子里，每個(gè)盒子里最多放 $9$ 個(gè)球。在這 $n$ 個(gè)盒子中指定 $k$ 個(gè)，其中每個(gè)盒子里至少放一個(gè)球。求方案數(shù)。

由于放進(jìn)的球數(shù)有上限，并不能用擋板法。

做法：枚舉分配到 $k$ 個(gè)非空盒子的球的總數(shù)，分別計(jì)算兩類盒子的放置方案數(shù)，這兩個(gè)計(jì)數(shù)問(wèn)題都可采用簡(jiǎn)單的DP解決。

總復(fù)雜度：$O(n^2+mn^3)$，$n$ 是等號(hào)左邊的數(shù)（加數(shù)）的個(gè)數(shù)，$m$ 是等號(hào)右邊數(shù)（和）的位數(shù)。

練習(xí)題

hihoCoder 1076 與鏈

Implementation

#include <bits/stdc++.h> using namespace std;const int N=105;long long dp[N][50]; const int mod=1e9+7;char s[N]; int c[2][50][500];void prep(int n) {c[1][0][0]=c[0][0][0]=1;for(int i=1; i<=n; i++){for(int j=i; j<=9*i; j++){for(int k=1; k<=min(9, j-i+1); k++){c[1][i][j]+=c[1][i-1][j-k], c[1][i][j]%=mod;}}for(int j=0; j<=9*i; j++){for(int k=0; k<=min(9, j); k++){c[0][i][j]+=c[0][i-1][j-k], c[0][i][j]%=mod;}}} }vector<int> a;int main() {int ma=0;for(; ; ){int len;scanf("%*[?]%n%[=+]", &len, s);a.push_back(len);ma=max(ma, len);if(s[0]=='='){break;}}int n;scanf("%s%n", s+1, &n);if(n<ma){puts("0");return 0;}prep(a.size());reverse(s+1, s+n+1);dp[0][0]=1;int carry=a.size();for(int i=1; i<=n; i++){int cnt1=0, cnt2=0;for(auto x: a){cnt1+=x==i;cnt2+=x>i;}for(int j=0; j<carry; j++)for(int k=0; k<carry; k++){int tot=s[i]-'0'+10*j-k;long long sum=0;for(int l=cnt1; l<=tot; l++){sum+=(long long)c[1][cnt1][l]*c[0][cnt2][tot-l];sum%=mod;}dp[i][j]+=dp[i-1][k]*sum;dp[i][j]%=mod;}}cout<<dp[n][0]<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Patt/p/6403556.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder 1367 等式填空的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。