[ARC153D] Sum of Sum of Digits
一眼數(shù)位DP,但多個數(shù)的進位問題不易維護。
在基數(shù)排序的過程中維護dp[i][j],其表示第i位讓j個數(shù)不進位的最優(yōu)方案。
因為dp[i+1]只依賴dp[i],所以采用兩個一維數(shù)組交替更新的方式實現(xiàn)。
在dp[i]更新dp[i+1]的過程中,外層從n到0枚舉j,內(nèi)層枚舉十進制{0,..9}。
標簽:
一眼數(shù)位DP,但多個數(shù)的進位問題不易維護。
在基數(shù)排序的過程中維護dp[i][j],其表示第i位讓j個數(shù)不進位的最優(yōu)方案。
因為dp[i+1]只依賴dp[i],所以采用兩個一維數(shù)組交替更新的方式實現(xiàn)。
在dp[i]更新dp[i+1]的過程中,外層從n到0枚舉j,內(nèi)層枚舉十進制{0,..9}。