当前位置 博文首页 > Keven_11的博客:C++题解:糖果
?????目录
题目?
题解
- ?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就是全局的最大收益。
代码:
cs#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; }
下一篇:没有了