Lightoj 1122 - Digit Count 【DP】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Lightoj 1122 - Digit Count 【DP】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1795字，纯文字阅读大概需要3分钟。
内容图文
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1122
题意：给你m个数，选取n个数组成一个整数，使得整数各位的最大数与最小数的差小于2。问有几种选法？
解法：ＤＰ。ｄｐ［ｉ］［ｊ］表示以ｊ结尾的ｉ位整数的解法数目。
答案即为ｓｕｍ（ｄｐ［ｎ］［ｋ］ （１＜＝ｋ＜＝９，且ｋ在集合Ｓ中） ）
代码：
#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
using
namespace
std;
int n, m;
int p[15];
int dp[15][15];
int main()
{
int t;
int cases = 1;
scanf("%d",&t);
while (t--)
{
memset(dp, 0, sizeof(dp));
memset(p, 0, sizeof(p));
scanf("%d%d", &m, &n);
int x;
for (int i = 1;i <= m;i++)
{
scanf("%d", &x);
p[x] = 1;
}
for (int i = 1;i <= 9;i++)
{
if (p[i])
dp[1][i] = 1;
}
for (int i = 2;i <= n;i++)
for (int j = 1;j <= 9;j++)
{
if (p[j]) dp[i][j] = 0;
for (int k = 1;k <= 9;k++)
{
if (abs(k - j) <= 2 && p[k])
dp[i][j] += dp[i-1][k];
}
}
int ans = 0;
for (int i = 1;i <= 9;i++)
if (p[i]) ans += dp[n][i];
printf("Case %d: %d\n", cases++, ans);
}
return0;
}
版权声明：转载请注明出处。
原文：http://blog.csdn.net/u014427196/article/details/47082191
内容总结
以上是互联网集市为您收集整理的Lightoj 1122 - Digit Count 【DP】全部内容，希望文章能够帮你解决Lightoj 1122 - Digit Count 【DP】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。