首页 > ACM题库 > HDU-杭电 > hdu 1987 Decoding-动态规划-[解题报告]C++
2013
12-26

hdu 1987 Decoding-动态规划-[解题报告]C++

Decoding

问题描述 :

Chip and Dale have devised an encryption method to hide their (written) text messages. They first agree secretly on two numbers that will be used as the number of rows (R) and columns (C) in a matrix. The sender encodes an intermediate format using the following rules:
1. The text is formed with uppercase letters [A-Z] and <space>.
2. Each text character will be represented by decimal values as follows:
<space> = 0, A = 1, B = 2, C = 3, …, Y = 25, Z = 26
The sender enters the 5 digit binary representation of the characters’ values in a spiral pattern along the matrix as shown below. The matrix is padded out with zeroes (0) to fill the matrix completely. For example, if the text to encode is: "ACM" and R=4 and C=4, the matrix would be filled in as follows:

The bits in the matrix are then concatenated together in row major order and sent to the receiver.
The example above would be encoded as: 0000110100101100

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing R (1<=R<=20), a space, C (1<=C<=20), a space, and a string of binary digits that represents the contents of the matrix (R * C binary digits).
The binary digits are in row major order.

输出:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing R (1<=R<=20), a space, C (1<=C<=20), a space, and a string of binary digits that represents the contents of the matrix (R * C binary digits).
The binary digits are in row major order.

样例输入:

4
4 4 0000110100101100
5 2 0110000010
2 6 010000001001
5 5 0100001000011010110000010

样例输出:

1 ACM
2 HI
3 HI
4 HI HO

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 105
#define mod 10000
#define INF 0x3f3f3f3f
using namespace std;

int n,m,ans;
int sx,sy,sp;
bool vis[maxn][maxn];
int mp[maxn][maxn];
int dp[maxn][maxn];
int dx[]={1,0};
int dy[]={0,1};
struct Node
{
    int x,y,p;
    bool operator <(const Node&xx) const
    {
        if(x!=xx.x) return x>xx.x;
        return y>xx.y;
    }
}cur,now;
priority_queue<Node>q;

void solve()
{
    int i,j,cnt,r,d;
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    cur.x=cur.y=1;
    cur.p=mp[1][1];
    vis[1][1]=1;
    q.push(cur);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        sx=now.x;
        sy=now.y;
        sp=now.p;
        cnt=sp;
        r=sx+sp;
        r=min(n,r);
        for(i=sx;i<=r;i++)
        {
            d=sy+cnt;
            d=min(d,m);
            for(j=sy;j<=d;j++)
            {
                if(i==sx&&j==sy) continue ;
                dp[i][j]+=dp[sx][sy];
                if(dp[i][j]>=mod) dp[i][j]%=mod;
                if(!vis[i][j])
                {
                    cur.x=i;
                    cur.y=j;
                    cur.p=mp[i][j];
                    vis[i][j]=1;
                    q.push(cur);
                }
            }
            cnt--;
        }
    }
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&mp[i][j]);
            }
        }
        solve();
        printf("%d\n",dp[n][m]);
    }
    return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define maxn 105
#define mod 10000
#define INF 0x3f3f3f3f
using namespace std;

int n,m,ans;
int mp[maxn][maxn];
int dp[maxn][maxn];

void solve()
{
    int i,j,p,q,r,d;
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            r=min(i+mp[i][j],n);
            for(p=i;p<=r;p++)
            {
                d=min(j+mp[i][j]-(p-i),m);
                for(q=j;q<=d;q++)
                {
                    if(p==i&&q==j) continue ;
                    dp[p][q]+=dp[i][j];
                    if(dp[p][q]>=mod) dp[p][q]%=mod;
                }
            }
        }
    }
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&mp[i][j]);
            }
        }
        solve();
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

解题转自:http://blog.csdn.net/tobewhatyouwanttobe/article/details/11827367


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

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.