当前位置 博文首页 > Keven_11的博客:C++题解:糖果

    Keven_11的博客:C++题解:糖果

    作者:[db:作者] 时间:2021-08-18 15:47

    ?????目录

    题目?

    题解


    题目?

    • ?3000ms
    • ?524288K

    DD 生活在一个城镇里,这个城镇上有?n?个糖果铺,其中第?i?个坐标是?(xi?,yi?),因为她很可爱,所以每当她经过一个糖果铺的时候店主就会送给她一个糖果,需要注意的是如果她多次经过同一个店铺是可以收获多颗糖的。她初始的时候站在原点上,每次可以选择前往一个除自己以外的店铺,但是 DD 很懒,她希望每次行走的距离的严格小于上一次行走的距离,她现在想知道自己最多可以收获多少个糖果

    输入格式

    第一行一个整数表示?n

    接下来?n?行每行两个整数表示?x_i,y_i

    输出格式

    输出 DD 最多可以收获多少个糖果

    输出时每行末尾的多余空格,不影响答案正确性

    要求使用「文件输入输出」的方式解题,输入文件为?candy.in,输出文件为?candy.out

    样例输入

    5
    5 8
    4 10
    3 1
    3 2
    3 3

    样例输出

    6

    题解:

    知识点:动态规划

    分析:

    题目要求下一条路的长度严格小于这一条路,那么我们可以从短的路到长的路来反着进行更新,这样可以保证距离长的边不会对距离短的边产生更新。

    设dpi,j?表示上一个点为i ,这一个点为j 时从j?出发继续走可以获得的最大收益;设fi?表示从点i ii出发继续走可以获得的最大收益,这里由于我们是从短到长进行更新的,所以f 表示的其实是走过的边小于当前边时的最大收益,当更新完时,f就是全局的最大收益。

    代码:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int maxn = 2005;
    int n;
    int x[maxn];
    int y[maxn];
    int dp[maxn][maxn];	// dp[i][j]表示从i到j这一条边i可以收获的最大值
    int f[maxn];		// f[i]表示从i点出发的可以收获的最大值
    struct Edge{
    	int u;//节点
    	int v;//节点
    	long long w;//价值
    	Edge() {};//一定要有
    	Edge(int a, int b){
    		u = a;
    		v = b;
    		w = pow(x[a] - x[b], 2) + pow(y[a] - y[b], 2);//欧几里得距离的平方
    	}
    }e[maxn * maxn + maxn];
    bool cmp(const Edge &x, const Edge &y){
    	return x.w < y.w;
    }
    int total = 0;//记第几个
    int main(){
    	freopen("candy.in","r",stdin);
        freopen("candy.out","w",stdout);
        scanf("%d", &n);
    	for (int i = 1; i <= n; i++){
    		scanf("%d%d", x + i, y + i);
    	}
    	for (int i = 1; i <= n; i++){//加边
    		e[total++] = Edge(0, i);
    	}
    	for (int i = 1; i <= n; i++){//加边
    		for (int j = i + 1; j <= n; j++){
    			e[total++] = Edge(i, j);
    			e[total++] = Edge(j, i);
    		}
    	}
    	sort(e, e + total, cmp);//排序
    	for (int i = 0; i < total; i++){
    		int j = i + 1;
    		while (e[j].w == e[i].w){//由于题目中要求路径严格递减,所以长度相同的边必须特殊考虑,即同时更新。先更新边,再更新点。
    			j++;
    		}
    		for (int k = i; k < j; k++){
    			int &dis = dp[e[k].u][e[k].v];
    			dis = max(dis, f[e[k].v] + 1);
    		}
    		for (int k = i; k < j; k++){
    			Edge &tmp = e[k];
    			f[tmp.u] = max(f[tmp.u], dp[tmp.u][tmp.v]);
    		}
    		i = j - 1;
    	}
    	printf("%d\n", f[0]);
        return 0;
    }

    cs
    下一篇:没有了