列表

详情

NC19890. [AHOI2012]收集资源

描述

在野外生存中，以最快、最省力的方式收集必要的生存资源是必须的。在这 次生存训练的尾声，给队员们的最后考核就是收集资源竞赛，要求队员们在限定 时间内收集到最多的资源。小龙抽到的地图是震后城市生存资源收集模拟，教官 为小龙发了一张地图，地图上的南北和东西方向各有N条间距相等的街道，如果 街道的交叉点即路口上标注着红点和数字，这代表该路口有一定量的资源可以收 集（如图4.1），否则表示该路口没有资源。小龙决定利用赛前准备时间好好研 究一下行走路线，根据地图上的比例尺提示，他知道从模拟城市的一个路口走到 临近的下一个路口，大概需要1分钟，而需要收集的资源就放在路口中心，拿起 来就可以继续行进，因此，行走需要时间，而收集资源的时间是可以忽略不计的。 请为小龙设计一个行走方案，使得他在限定时间内能收集到最多的资源。
 

输入描述

共M+1行，第一行为三个整数N，M，T（1 ≤ N,M,T ≤ 200，中间用空格分 开），分别为地图大小N，有资源的路口的数量M和收集资源的时间T分 钟。
接下来M行，每行三个整数Xi、Yi、Vi(中间用空格分开，且均为整数,Xi,Yi为第i个有资源的地点的坐标，0 ≤ Xi,Yi ≤ N-1,Vi为其资源数量1 ≤ Vi ≤ 200

输出描述

一个正整数，在时间T分钟内可收集到的最多资源总数。
（注：假设从某个交叉点出发，沿着南北方向或东西方向行走到下一个街道的交叉点需要时间固定为1分钟；每个队员必须从（0,0）点出发，结束时不要求回到出发点。如果在时间结束时恰好到达某一处有资源的坐标点，则该资源计入收集量。）

示例1

输入: 

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

输出: 

28

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++(g++ 7.5.0) 解法, 执行用时: 426ms, 内存消耗: 540K, 提交时间: 2023-03-19 16:32:56 

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

void read(int &x) {

    char ch; bool ok;

    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

void print(int x){

    if(x<0)putchar('-'),x=-x;

    if(x>9)print(x/10);

    putchar(x%10+'0');

}

#define rg register

const int maxn=210;

int n,m,T,ans,d[maxn][maxn];bool vis[maxn];

struct oo{int x,y,v;}a[maxn];

void dfs(int x,int now,int val)

{

    if(now<=T)ans=max(ans,val);

    else return ;

    for(rg int i=1;i<=m;i++)

        if(d[x][i]&&!vis[i])

            vis[i]=1,dfs(i,now+d[x][i],val+a[i].v),vis[i]=0;

}

int main()

{

    read(n),read(m),read(T);

    for(rg int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].v);

    for(rg int i=0;i<=m;i++)

        for(rg int j=0;j<=m;j++)

            if(i!=j) 

            {

                bool flag=0;

                for(rg int k=1;k<=m;k++)

                    if(k!=i&&k!=j)

                    {

                        int lx=min(a[i].x,a[j].x),rx=max(a[i].x,a[j].x),ly=min(a[i].y,a[j].y),ry=max(a[i].y,a[j].y);

                        if(a[k].x>=lx&&a[k].x<=rx&&a[k].y>=ly&&a[k].y<=ry){flag=1;break;}

                    }

                if(!flag)d[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);

            }

    dfs(0,0,0);printf("%d\n",ans);

}

C++14(g++5.4) 解法, 执行用时: 354ms, 内存消耗: 580K, 提交时间: 2020-09-28 19:23:45 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn = 210;

struct node{

    int x,y,w;

}a[maxn];

int n,m,t;

int dis[maxn][maxn];

bool check(int i,int j){

    int lx = min(a[i].x,a[j].x);

    int ly = min(a[i].y,a[j].y);

    int rx = max(a[i].x,a[j].x);

    int ry = max(a[i].y,a[j].y);

    for(int k=1;k<=m;k++){

        if(k==i||k==j) continue;

        if(a[k].x>=lx&&a[k].x<=rx&&a[k].y>=ly&&a[k].y<=ry) return 0;

    }

    return 1;

}

int ans,vis[maxn];

void dfs(int x,int res,int sum){

    ans = max(ans,sum);

    for(int i=1;i<=m;i++){

        if(x==i||vis[i]) continue;

        if(res-dis[x][i]<0) continue;

        vis[i] = 1;

        dfs(i,res-dis[x][i],sum+a[i].w);

        vis[i] = 0;

    }

}

int main(){

//  freopen("123.txt","r",stdin);

    scanf("%d%d%d",&n,&m,&t);

    memset(dis,0x3f,sizeof dis);

    m++;

    dis[1][1] = 0;

    for(int i=2;i<=m;i++){

        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);

        dis[i][i] = 0;

    }

    for(int i=1;i<=m;i++){

        for(int j=i+1;j<=m;j++){

            if(check(i,j))

            dis[i][j] = dis[j][i] = min(dis[i][j],abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));

        }

    }

    dfs(1,t,0);

    printf("%d",ans);

}

C++11(clang++ 3.9) 解法, 执行用时: 478ms, 内存消耗: 492K, 提交时间: 2019-04-30 20:15:00 

#include<iostream>

#include<cstdio>

#include<ctype.h>

#include<cmath>

using namespace std;

inline int read(){

    int x=0,f=0;char ch=getchar();

    while(!isdigit(ch))f|=ch=='-',ch=getchar();

    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();

    return f?-x:x;

}

struct OOO {

    int x,y,w;

}a[205];

int n,m,T,ans,g[205][205],vis[205];

inline bool check(int x,int y){//哇哦，太漂亮的优化 

    int lx=max(a[x].x,a[y].x),ly=max(a[x].y,a[y].y),rx=a[x].x+a[y].x-lx,ry=a[x].y+a[y].y-ly;

    for(int i=0;i<=m;++i)if(i!=x && i!=y && a[i].x>=rx && a[i].x<=lx && a[i].y>=ry && a[i].y<=ly)return false;

    return true;

}

void dfs(int x,int t,int sum){

    ans=max(sum,ans);

    for(int i=0;i<=m;++i)

        if(g[x][i] && t+g[x][i]<=T && !vis[i])

            vis[i]=1,dfs(i,t+g[x][i],sum+a[i].w),vis[i]=0;

}

int main(){

    n=read(),m=read(),T=read();

    for(int i=1;i<=m;i++)a[i].x=read(),a[i].y=read(),a[i].w=read();   

    for(int i=0;i<=m;i++)

        for(int j=0;j<=m;j++)

            if(i!=j && check(i,j))g[i][j]=abs(a[j].y-a[i].y)+abs(a[j].x-a[i].x);

    dfs(0,0,0);

    printf("%d\n",ans);

    return 0;

}

上一题

© 2025 nowcoder.com