首页 > ACM题库 > HDU-杭电 > hdu 2379 Dice Password Security-动态规划-[解题报告]C++
2014
01-05

hdu 2379 Dice Password Security-动态规划-[解题报告]C++

Dice Password Security

问题描述 :

NCIM Group sponsored problem.

The NCIM Group does a lot of work on IT solutions in defense and security. Good security usually starts with picking a strong password. Generating a password at random is generally a good practice. For example, a password like "2R4eZ9Rqup" is a bit harder to guess than "god", "love", "sex" or "secret".

The problem with passwords consisting of random letters and digits is that they are hard to remember. Instead of using letters and digits it is also possible to generate passwords by putting random words together. Words are easier to remember than letters and digits.

Using a dictionary of 7776 (65) words, a 5-random-word password is about as strong as a 11-random-character password.

77765 = 28430288029929701376 ≈ 3 * 1019

6211 = 52036560683837093888 ≈ 5 * 1019

Some applications hide the password you are typing on the screen by printing dots or asterisks. This allows someone watching your screen to count the number of characters in your password. The NCIM Group wants you to find out whether or not this compromises the strength of your password.

You must write a program that calculates the number of possible passwords that can be generated given:

the dictionary of words, the amount of words used to generate the password and the length of the password.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with three positive integers m (1 <= m <= 7776), n (1 <= n <= 5) and q (1 <= q <= 20): the number of words in the dictionary, the number of words to generate the password, and the number of queries, respectively.

The dictionary: m lines each containing one word wi Each word consists only of lowercase letters. The length of each word will be between 3 and 10 inclusive. No word in the dictionary will be a substring of another word in the dictionary.

q lines each containing a positive integer lj (1 <= lj <= 50), the length observed.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with three positive integers m (1 <= m <= 7776), n (1 <= n <= 5) and q (1 <= q <= 20): the number of words in the dictionary, the number of words to generate the password, and the number of queries, respectively.

The dictionary: m lines each containing one word wi Each word consists only of lowercase letters. The length of each word will be between 3 and 10 inclusive. No word in the dictionary will be a substring of another word in the dictionary.

q lines each containing a positive integer lj (1 <= lj <= 50), the length observed.

样例输入:

1
4 2 2
aap
noot
mies
piet
7
8

样例输出:

6
9

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2915

                    http://acm.hdu.edu.cn/showproblem.php?pid=2379

题目的意思就是给定一些单词,可以用这些单词的任意组合作为密码。求一个密码长度为l,恰好由k个给定的单词组成的种数。

是个动态规划的题目,题目很好理解,用dp[i][j]表示由i个单词组成长度为j的密码的种数,则dp[i+1][j+k]=dp[i][j]*cnt[k](1<k<10)则本题就比较简单了。

因为单词个数最大为5即L,密码长度最大为50即LEN,单词长度最大为10即K,所以时间复杂度为O(L*LEN*K)。cnt【k】表示长度为k的单词总共由多少个。

代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

const int LEN=52;
const int N=7;

__int64 dp[N][LEN];
int cnt[11];

int main()
{
    int t,m,n,q,i,k,j,l;
    scanf("%d",&t);
    string a;
    while (t--)
    {
        scanf("%d%d%d",&m,&n,&q);
        while (m--)
        {
            cin>>a;
            cnt[a.length()]++;
        }
        memset(dp,0,sizeof(dp));
        for (i=1;i<=10;i++)
        {
            dp[1][i]=cnt[i];
            dp[i][i]=cnt[1];
        }
		for (i=0;i<5;i++)
        {
            for (k=0;k<=10;k++)
            {
                for (j=0;j<=LEN-k;j++)
                {
                    dp[i+1][j+k]+=dp[i][j]*cnt[k];
                }
            }
        }
        while (q--)
        {
            scanf("%d",&l);
            printf("%I64d\n",dp[n][l]);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/iaccepted/article/details/6719507


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。