递推DP URAL 1353 Milliard Vasya's Function

题目传送门

 /*
题意:1~1e9的数字里,各个位数数字相加和为s的个数
递推DP:dp[i][j] 表示i位数字,当前数字和为j的个数
状态转移方程:dp[i][j] += dp[i-1][j-k],为了不出现负数
改为:dp[i][j+k] += dp[i-1][j]
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
int dp[][]; int main(void) //URAL 1353 Milliard Vasya's Function
{
//freopen ("F.in", "r", stdin); int s;
while (scanf ("%d", &s) == )
{
memset (dp, , sizeof (dp)); dp[][] = ;
for (int i=; i<=; ++i)
{
for (int j=; j<=s; ++j)
{
if (dp[i-][j])
{
for (int k=; k<=; ++k) dp[i][j+k] += dp[i-][j];
} }
} if (s == ) dp[][s] += ;
printf ("%d\n", dp[][s]);
} return ;
}
上一篇:Spring实战——XML和JavaConfig的混合配置


下一篇:203. Remove Linked List Elements