首页 > ACM题库 > HDU-杭电 > hdu 2471 History of Languages-动态规划-[解题报告]C++
2014
01-26

hdu 2471 History of Languages-动态规划-[解题报告]C++

History of Languages

问题描述 :

We are examining two specific classes of languages (a possibly infinite set of
strings) in this problem. Fortunately (or maybe unfortunately), we are not given the strings contained in each language directly, rather we are given two deterministic finite automatons that describe such languages.

Your task here is simple: to determine if the languages described by the two automatons are the same.

输入:

There are multiple test cases in the input file.
The first line of each test case is one integer, T ( 2 ÷ T ÷ 26), the size of the alphabet. In each test case, the description of automaton A comes before that of automaton B. The description of each automaton starts with one line containing N (1 ÷ N ÷ 2000 ), the number of states in the automaton, followed by N lines, each line of the format: F, X0, X1, ˇ, XT-1, ,-1 ÷ Xi < N). If F = 1, then the state is an accepting state; also, if Xi = -1, it means that the state has no corresponding transition available for character i. The start state of both finite automatons will always be state 0.

Two successive test cases are separated by a blank line. A case with a single 0 indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
The first line of each test case is one integer, T ( 2 ÷ T ÷ 26), the size of the alphabet. In each test case, the description of automaton A comes before that of automaton B. The description of each automaton starts with one line containing N (1 ÷ N ÷ 2000 ), the number of states in the automaton, followed by N lines, each line of the format: F, X0, X1, ˇ, XT-1, ,-1 ÷ Xi < N). If F = 1, then the state is an accepting state; also, if Xi = -1, it means that the state has no corresponding transition available for character i. The start state of both finite automatons will always be state 0.

Two successive test cases are separated by a blank line. A case with a single 0 indicates the end of the input file, and should not be processed by your program.

样例输入:

2
3
1 -1 1
0 -1 2
0 -1 0
2
1 -1 1
0 -1 0
3
4
1 -1 -1 1
1 -1 -1 2
1 -1 -1 3
1 -1 -1 1
2
1 -1 -1 1
1 -1 -1 0
0

样例输出:

Case #1: No
Case #2: Yes

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2571

简单dp,

dp[n][m] +=(  dp[n-1][m],dp[n][m-1],d[i][k] )

k 为m的因子

PS:0边界要初始为负数(例如-123456789)越大越好

代码:

#include <stdio.h>
#include <string.h>

int dp[25][1005];

#define max(x,y) x > y ? x : y

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        int i,j;
        int n,m;
        scanf("%d%d",&n,&m);
        for(i = 0;i <=m; i++)
                dp[0][i] = -123456789;
         for(i = 0;i <=n; i++)
                dp[i][0] = -123456789;
        dp[0][1] = 0;
        dp[1][0] = 0;

        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
                scanf("%d",&dp[i][j]);
        int k = 0;
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
            {
                int dp_ans = max(dp[i-1][j],dp[i][j-1]);
                for(k = 1; k < j; k++)
                    if(j % k == 0)
                       dp_ans = max(dp_ans,dp[i][k]);
                dp[i][j] += dp_ans;
            }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/yyroom/archive/2013/07/26/3217527.html


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。