首页 > ACM题库 > HDU-杭电 > hdu 2571 命运-动态规划-[解题报告]C++
2014
02-10

hdu 2571 命运-动态规划-[解题报告]C++

命运

问题描述 :

穿过幽谷意味着离大魔王lemon已经无限接近了!
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:

yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。

输入:

输入数据首先是一个整数C,表示测试数据的组数。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。

输出:

输入数据首先是一个整数C,表示测试数据的组数。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。

样例输入:

1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10

样例输出:

52

#include<iostream>
#include<cstdio>
using namespace std;

int a[25][1005];
int dp[25][1005];

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
        int n,m;
        cin>>n>>m;
        int i,j,k;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);

        for(i=0;i<m;i++)
            dp[0][i]=-105;
        for(i=0;i<n;i++)
            dp[i][0]=-105;
        dp[0][1]=dp[1][0]=0;

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //(x+1,y),(x,y+1)
                for(k=2;k<=m;k++)
                {
                    if(j%k==0)
                        dp[i][j]=max(dp[i][j],dp[i][j/k]);   //(x,y*k)
                }
                dp[i][j]+=a[i][j];
            }

        cout<<dp[n][m]<<endl;
    }
    return 0;
}

/*
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char str[105];
int dp[105][2];   //dp[i][1]表示完成i打印Cap灯亮,dp[i][0]表示完成i打印Cap灯灭

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
       cin>>str+1;
       int i;
       int len=strlen(str+1);
       dp[0][0]=0,dp[0][1]=2;   //初始状态为灯灭
       for(i=1;i<=len;i++)
       {
           if(str[i]>='A'&&str[i]<='Z')   //为大写
           {
               dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+2);
               dp[i][0]=min(dp[i-1][1]+2,dp[i-1][0]+2);
           }
           else     //为小写
           {
               dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+2);
               dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+2);
           }
       }

       int res=min(dp[len][0],dp[len][1]+1);
       cout<<res<<endl;
    }
    return 0;
}

/*
3
Pirates
HDUacm
HDUACM
*/

解题转自:http://blog.csdn.net/coraline_m/article/details/18670803


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”