首页 > ACM题库 > HDU-杭电 > HDU 3028-Robot-动态规划-[解题报告]HOJ
2014
02-27

HDU 3028-Robot-动态规划-[解题报告]HOJ

Robot

问题描述 :

There are n places (numbered 1,2,…,n), and at any second X, in place A, it will appear k robots. Now you have normal weapons. If at the second X and you are in place A, you will distroy those k robots. Otherwise, you have a special weapon (named O4), if you at second X in the place A and use O4, you will destroy all the robots which appear in the place adjoining to A (OF COUSE include the place A). You move from place A to B (B adjoins to A) must use some second;

Now you have T second ,and ask you two questions:

1. if you have an O4, how many robots can you destroy?(the maximum number);
2. if you don’t have O4 but weapons, how many robots can you destroy?(the maximum number);

输入:

First line: n, m, T. (n is the number of place, m is the number of roads between place, T is the seconds you have), n ≤ 100, m ≤ 2500, t ≤ 1000;

From 2 to m + 1 line: every line contains 3 integers, P, Q, D, indicating that moving from place P to place Q will use D seconds (the roads are undirection);

Next every line contains 3 integers, X, A, K, indicating at the X second, the place A will appear K robots;

The last line contains three "0" indicating that the case is end;

输出:

First line: n, m, T. (n is the number of place, m is the number of roads between place, T is the seconds you have), n ≤ 100, m ≤ 2500, t ≤ 1000;

From 2 to m + 1 line: every line contains 3 integers, P, Q, D, indicating that moving from place P to place Q will use D seconds (the roads are undirection);

Next every line contains 3 integers, X, A, K, indicating at the X second, the place A will appear K robots;

The last line contains three "0" indicating that the case is end;

样例输入:

3 2 10
1 2 1
2 3 2
1 1 1
2 2 2
3 3 3
4 1 4
2 3 3
4 2 2
6 1 4
8 2 3
10 2 2
9 1 1
7 1 5
3 2 2
8 1 8
0 0 0

样例输出:

32 29

#include<cstdio>
#include<set>
#include<cstring>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int dp[1005][105][2];//dp[i][j] 第i秒在第j点时的最大值
int times[105][1005];//times[i][j] i点在j秒有times[i][j]机器人出现
int alltime[105][1005];//alltime[i][j]预处理i点在j秒本身与相邻点所有的机器人
struct node
{
    int x,t;
    bool operator < (const node &a) const
    {
        return x<a.x;
    }
} temp;
set<node> line[105];
int check(int x,int t)
{
    //x相邻及本身在t秒的机器人数
    int sumt=0;
    for(set<node>::iterator it=line[x].begin(); it!=line[x].end(); ++it)
        sumt+=times[it->x][t];
    return sumt+times[x][t];
}
int main()
{
    int n,m,t,p,q,d,x,a,k;
    for(; ~scanf("%d%d%d",&n,&m,&t);)
    {
        int maxx[2];
        maxx[0]=maxx[1]=0;
        memset(dp,-1,sizeof(dp));
        memset(times,0,sizeof(times));
        for(int i=0; i<=n; ++i) line[i].clear();
        //邻接表储存边
        for(int i=0; i<m; ++i)
        {
            scanf("%d%d%d",&p,&q,&d);
            temp.t=d;
            temp.x=q;
            line[p].insert(temp);
            temp.x=p;
            line[q].insert(temp);
        }
        for(;scanf("%d%d%d",&x,&a,&k);)
        {
            if(x+a+k==0)  break;
            times[a][x]+=k;
        }
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=t; ++j)
                alltime[i][j]=check(i,j);
        for(int i=1; i<=n; ++i)
        {
            dp[1][i][0]=times[i][1];
            dp[1][i][1]=alltime[i][1];
        }
        for(int i=1; i<=t; ++i)
            for(int j=1; j<=n; ++j)
            {
                if(dp[i][j][0]!=-1)
                {
                    for(set<node>::iterator it=line[j].begin(); it!=line[j].end(); ++it)
                    {
                        if(i+it->t<=t)//转移到相邻点且目标时间不超范围
                        {
                            //从未使用O4的状态出发到相邻的点且在相邻点不使用O4
                            dp[i+it->t][it->x][0]=max(dp[i+it->t][it->x][0],dp[i][j][0]+times[it->x][i+it->t]);
                            //从未使用O4的状态出发到相邻的点且在相邻点使用O4
                            dp[i+it->t][it->x][1]=max(dp[i+it->t][it->x][1],dp[i][j][0]+alltime[it->x][i+it->t]);
                            //从使用O4的状态出发到相邻的点且在相邻点不使用O4
                            dp[i+it->t][it->x][1]=max(dp[i+it->t][it->x][1],dp[i][j][1]+times[it->x][i+it->t]);
                            //刷新最大值
                            maxx[0]=max(maxx[0],dp[i+it->t][it->x][0]);
                            maxx[1]=max(maxx[1],dp[i+it->t][it->x][1]);
                        }
                    }
                    if(i+1<=t)//停留在当前点的情况
                    {
                        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+times[j][i+1]);
                        dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][0]+alltime[j][i+1]);
                        dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][1]+times[j][i+1]);
                        maxx[0]=max(maxx[0],dp[i+1][j][0]);
                        maxx[1]=max(maxx[1],dp[i+1][j][1]);
                    }
                }
            }
        printf("%d %d\n",maxx[1],maxx[0]);
    }
    return 0;
}

参考:http://blog.csdn.net/acm_ted/article/details/7840341


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。