首页 > ACM题库 > HDU-杭电 > HDU 2751-HOJ-Cranes-动态规划-[解题报告]C++
2014
02-14

HDU 2751-HOJ-Cranes-动态规划-[解题报告]C++

Cranes

问题描述 :

A crane is a wonderful tool for putting up a building. It makes the job go very quickly. When the building must go up even faster, more than one crane can be used. However, when there are too many cranes working on the same building, it can get dangerous. As the cranes spins around, it can bump into another crane if the operator is not careful. Such an accident could cause the cranes to fall over, possibly causing major damage. Therefore, safety regulations require cranes to be spaced far enough apart so that it is impossible for any part of a crane to touch any part of any other crane. Unfortunately, these regulations limit the number of cranes that can be used on the construction site, slowing down the pace of construction. Your task is to place the cranes on the construction site while respecting the safety regulations.

The construction site is laid out as a square grid. Several places on the grid have been marked as possible crane locations. The arm of each crane has a certain length r, and can rotate around the location of the crane. The crane covers the entire area that is no more than r units away from the location of the crane. You are to place the cranes to maximize the total area covered by all the cranes.

输入:

The first line of each test chunk contains one integer specifying the number of test cases in this chunk to follow. Each test case begins with a line containing an integer C, the number of possible locations where a crane could be placed. There will be no more than 15 such locations. Each of the following C lines contains three integers x, y, and r, all between -10 000 and 10 000 inclusive. The first two integers are the grid coordinates of the location, and the third integer is the length of the arm of the crane that can be placed at that location.
Please process to the end of the data file.

输出:

The first line of each test chunk contains one integer specifying the number of test cases in this chunk to follow. Each test case begins with a line containing an integer C, the number of possible locations where a crane could be placed. There will be no more than 15 such locations. Each of the following C lines contains three integers x, y, and r, all between -10 000 and 10 000 inclusive. The first two integers are the grid coordinates of the location, and the third integer is the length of the arm of the crane that can be placed at that location.
Please process to the end of the data file.

样例输入:

1
3
0 0 4
5 0 4
-5 0 4
1
3
0 0 4
5 0 4
-5 0 4

样例输出:

32
32

/*
* 题意:给出一个带权值的矩阵,从左上角走
* 到右下角,问怎样走才能使总权值最大; 
* 行走的要求 :如果当前格子是(x,y),
* 下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。 
*  
* 思路:DP,状态转移方程:
* sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];
* 其中1<=k<=j-1,且k是j的因子或k=j-1,即向右走一格    
*
*/

#include<stdio.h>
#define MIN -10000000
int num[22][1002],n,m;
int dp[22][1002];
void initi()
{
    for(int i=0;i<=m;i++)
        dp[0][i]=MIN;
    for(int i=0;i<=n;i++)
        dp[i][0]=MIN;
}
int getMax(int x,int y)
{
    int Max=dp[x][y-1];
    if(dp[x-1][y]>Max)
        Max=dp[x-1][y];
    if(x==1&&y==1)
        return 0;
    for(int i=1;i<y;i++)
    {
        if(y%i==0)
            if(dp[x][i]>Max)
                Max=dp[x][i];
    }
    return Max;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int i,j;
        scanf("%d%d",&n,&m);
        initi();
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&num[i][j]);
        dp[1][1]=num[1][1];
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                    dp[i][j]=num[i][j]+getMax(i,j);
        printf("%d\n",dp[n][m]);    
    }
    return 0;
}

解题参考:http://blog.csdn.net/joy_go/article/details/7974598


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.