关键词:
意思大致为从1-10^9数中找到位数和为s的个数
分析:利用动态规划思想,一位一位的考虑,和s的范围为1-81
状态定义:dp[i][j] = 当前所有i位数的和为j的个数
除了最高位的取值为1-9(最高位不能为0),其余位的取值都为0-9,所有我们可以最开始初始化dp[1][j](1 <= j <= 9) = 1.假如我们求dp[5][9]当前所有5位数的和为9的个数,那么我们需要考虑0-9这10个数的情况,
如果此时个位(即第5位)的值为6,那么我们需要得知dp[4][9-6]的值,因为和为9,且此时个位(第五位)为6,那么前4个数和必须为3才满足和为9,那么dp[5][9] += d[5-1][9-6];
由此很容易得到状态转移方程:dp[i][j] = dp[i-1][j-k];
注意!!!:1000000000不能忽视,最后和为1的结果必须再加1;
代码:
#include<bits/stdc++.h> using namespace std; int dp[10][81]; int main() memset(dp, 0, sizeof(dp)); for(int i = 1; i <= 9; i++) dp[1][i] = 1; for(int i = 2; i < 10; i++) int c = i*9; for(int j = 1; j <= c; j++) for(int k = 0; k < j && k <= 9; k++) dp[i][j] += dp[i-1][j-k]; for(int i = 2; i <= 9; i++) for(int j = 1; j <= 81; j++) dp[i][j] += dp[i-1][j]; dp[9][1]++;//1000000000的情况 int s; while(scanf("%d", &s) == 1) printf("%d\n", dp[9][s]); return 0;
lq0269土地测量水题(代码片段)
...题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。造成高房价的原因有许多,比如土地出让价格。既然地价高,土地的面积必须仔细计算。遗憾的是,有些地块的形状... 查看详情
lq0269土地测量水题(代码片段)
...题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。造成高房价的原因有许多,比如土地出让价格。既然地价高,土地的面积必须仔细计算。遗憾的是,有些地块的形状... 查看详情
nyoj吃土豆(代码片段)
吃土豆时间限制:1000 ms | 内存限制:65535 KB难度:4 描述Bean-eatingisaninterestinggame,everyoneownsanM*Nmatrix,whichisfilledwithdifferentqualitiesbeans.Meantime,thereisonlyonebeaninany1*1grid.N 查看详情
nyoj-0708-ones(代码片段)
nyoj-0708-ones题意:用1,+,*,(,).这四个符号组成表达式表达数s(0<=s<=10000),且1最少时1的的个数状态转移方程:dp[i]=min(dp[i-1]+1,dp[j]+dp[i-j]);代码:#include<bits/stdc++.h>usingnamespacestd;constintN=100001;intdp[N];intmain() 查看详情
nyoj圈水池(代码片段)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;structnodeintx,y;;nodevex[1000];//存入的所有的点nodestackk[1000];//凸包中所有 查看详情
nyoj单词拼接(代码片段)
#include<iostream>#include<string>#include<string.h>#include<queue>#include<stdio.h>#include<math.h>#include<algorithm>usingnamespacestd;#defineMAX2005intfirs 查看详情
nyoj484-thefamousclock(代码片段)
484-TheFamousClock内存限制:64MB时间限制:1000ms特判:No通过数:2提交数:2难度:1题目描述:Mr.B,Mr.GandMr.MarenowinWarsaw,Poland,forthe2012’sACM-ICPCWorldFinalsContest.They’vedecidedtotakea5hourstrainingeverydaybeforethecontest.A 查看详情
nyoj-158-省赛来了(组合数)(代码片段)
题目链接1/*2Name:nyoj-158-省赛来了3Copyright:4Author:5Date:2018/4/2517:07:226Description:7暴力,秒天秒地8*/9#include<iostream>10#include<cstdio>11usingnamespacestd;12longlongc[1000][1000];13intmain()141 查看详情
nyoj棋盘覆盖(代码片段)
数字很大,要用大数乘法。 #include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;chars1[1000];chars2[10];char*bignum(char*num1,c 查看详情
nyoj-211-cowcontest(floyd算法)(代码片段)
题目链接1/*2Name:nyoj-211-CowContest3Copyright:4Author:5Date:2018/4/2721:02:066Description:7floyd算法8大佬的惊奇思路9*/10#include<iostream>11#include<cstdio>12#include<cstring>13usingnamespacestd 查看详情
nyoj61传纸条(代码片段)
双线DP#include<iostream>#include<algorithm>#include<ctype.h>#include<string>#include<string.h>#include<vector>#include<queue>usingnamespacestd;intdp[110][55][55 查看详情
nyoj迷宫寻宝(代码片段)
#include<iostream>#include<string>#include<string.h>#include<queue>#include<stdio.h>#include<math.h>#include<algorithm>usingnamespacestd;chard[30][30];inta[5] 查看详情
nyoj208+poj1456supermarket(贪心)(代码片段)
Supermarket时间限制:1000ms | 内存限制:65535KB难度:4 描述AsupermarkethasasetProdofproductsonsale.Itearnsaprofitpxforeachproductx∈Prodsoldbyadeadlinedxthatismeasuredasanintegralnumberoftimeunitsstart 查看详情
nyoj会场安排问题(代码片段)
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;structHYintu,v;hy[10005];boolcmp(HYa,HYb)if(a.v==b.v)returna.u 查看详情
nyoj-115-城市平乱(dijkstra算法)(代码片段)
题目链接1/*2Name:nyoj-115-城市平乱3Copyright:4Author:5Date:2018/4/2517:28:066Description:7dijkstra模板题8枚举从部队所在的城市到叛乱城市取最小值9*/10#include<iostream>11#include<cstdio>12#include<cstring>13# 查看详情
nyoj5binarystringmatching(代码片段)
BinaryStringMatching时间限制:3000ms | 内存限制:65535KB|难度:3 描述 GiventwostringsAandB,whosealphabetconsistonly‘0’and‘1’.YourtaskisonlytotellhowmanytimesdoesAappearasasubstringofB?Forexample,thet 查看详情
nyoj鏂规鏁伴噺(代码片段)
鏍囩锛?ahref='http://www.mamicode.com/so/1/end'title='end'>end stdio.h == wrong 閫掓帹 style || &n 查看详情
nyoj开心的小明(代码片段)
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;intd[30][30005];//d[i][j]i件中,j重量的物品,价格最高intv[30],w[30];intMax(int 查看详情