首页 > ACM题库 > HDU-杭电 > HDU 3687-National Day Parade-动态规划-[解题报告]HOJ
2014
11-30

HDU 3687-National Day Parade-动态规划-[解题报告]HOJ

National Day Parade

问题描述 :

There are n×n students preparing for the National Day parade on the playground. The playground can be considered as a n×m grid. The coordinate of the west north corner is (1,1) , and the coordinate of the east south corner is (n,m).
Traffic Real Time Query System

When training, every students must stand on a line intersection and all students must form a n×n square. The figure above shows a 3×8 playground with 9 students training on it. The thick black dots stand for the students. You can see that 9 students form a 3×3 square.

After training, the students will get a time to relax and move away as they like. To make it easy for their masters to control the training, the students are only allowed to move in the east-west direction. When the next training begins, the master would gather them to form a n×n square again, and the position of the square doesn’t matter. Of course, no student is allowed to stand outside the playground.

You are given the coordinates of each student when they are having a rest. Your task is to figure out the minimum sum of distance that all students should move to form a n×n square.

输入:

There are at most 100 test cases.
For each test case:
The first line of one test case contain two integers n,m. (n<=56,m<=200)
Then there are n×n lines. Each line contains two integers, 1<=Xi<=n,1<= Yi<=m indicating that the coordinate of the ith student is (Xi , Yi ). It is possible for more than one student to stand at the same grid point.

The input is ended with 0 0.

输出:

There are at most 100 test cases.
For each test case:
The first line of one test case contain two integers n,m. (n<=56,m<=200)
Then there are n×n lines. Each line contains two integers, 1<=Xi<=n,1<= Yi<=m indicating that the coordinate of the ith student is (Xi , Yi ). It is possible for more than one student to stand at the same grid point.

The input is ended with 0 0.

样例输入:

2 168
2 101
1 127
1 105
2 90
0 0

样例输出:

41

在N*M的矩阵里,分布了,N*N个人,每行N个,且只能左右移动,求把所有人合并成N*N正方形所需的最小代价。

因为每个人只能在本行移动,所以预处理出来每行的每种合并方式,再判断列的

#include "stdio.h"
#include "string.h"
#include "iostream"
#include "algorithm"
using namespace std;

int inf=0x3f3f3f3f;

int Fabs(int a)
{
    if (a<0) return -a; else return a;
}

int Min(int a,int b)
{
    if (a<b) return a;
    else return b;
}

struct node
{
    int num;
    int x[210];
}mark[210];

int main()
{
    int n,m,i,j,k,sum,ans;
    int dp[210][210];
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        if (n==0 && m==0) break;
        memset(mark,0,sizeof(mark));
        for (i=1;i<=n*n;i++)
        {
            scanf("%d%d",&j,&k);
            mark[j].num++;
            mark[j].x[mark[j].num]=k;
        }
        for (i=1;i<=n;i++)
            sort(mark[i].x+1,mark[i].x+1+n);

        memset(dp,0,sizeof(dp));

        for (i=1;i<=n;i++)
            for (j=1;j<=m-n+1;j++)
                for (k=1;k<=n;k++)
                    dp[i][j]+=Fabs(mark[i].x[k]-j-k+1);

        ans=inf;
        for (j=1;j<=m-n+1;j++)
        {
            sum=0;
            for (i=1;i<=n;i++)
                sum+=dp[i][j];
            ans=Min(sum,ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/u011932355/article/details/39961335


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

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