苏州工业园区两学一做网站,外贸推广系统,卡一卡二卡三入口2021,自助建站模板分析#xff1a;暴力挺好打的#xff0c;对于前30%的数据神搜#xff0c;hi相同的数据将所有的建筑按照c从小到大排序#xff0c;看最多能跳多少,ci0的数据将所有的建筑按照h从小到大排序#xff0c;枚举起点和终点#xff0c;看能否跳这么多,取个max就可以了.这样70分就… 分析暴力挺好打的对于前30%的数据神搜hi相同的数据将所有的建筑按照c从小到大排序看最多能跳多少,ci0的数据将所有的建筑按照h从小到大排序枚举起点和终点看能否跳这么多,取个max就可以了.这样70分就到手了. 部分分的提示还是比较明显的要消除一个参数的影响那么就按照h从小到大排序显然只有可能顺着跳过城市不能跳过去又跳回来.那么就是一个比较简单的dp了f[i][j]表示跳了i次最后一次跳到j的最小花费转移的话枚举j之前的k就能转移了最后倒叙枚举i看哪一个f[i][j]T就可以了. 多个参数有影响的常见策略是消除一个参数的影响常见的办法就是排序,如果一个点不能经过多次那么就想一个办法让它强行不经过这个点. 暴力 #include cstdio
#include cmath
#include cstring
#include iostream
#include algorithmusing namespace std;int n, T, ans, vis[1010];
bool flag1 true, flag2 true;struct node
{int c, h;
}e[55];bool cmp1(node a, node b)
{return a.c b.c;
}bool cmp2(node a, node b)
{return a.h b.h;
}void dfs(int u, int sum,int tot)
{ans max(ans, tot 1);vis[u] 1;for (int i 1; i n; i){if (!vis[i]){int huafei abs(e[i].h - e[u].h) e[u].c;if (sum huafei T)dfs(i, sum huafei, tot 1);}}
}int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%d, e[i].c);if (e[i].c ! 0)flag2 false;}for (int i 1; i n; i){scanf(%d, e[i].h);if (i ! 1 e[i].h ! e[i - 1].h)flag1 false;}scanf(%d, T);if (n 5 || (!flag1 !flag2)){for (int i 1; i n; i){memset(vis, 0, sizeof(vis));dfs(i,0,0);}printf(%d\n, ans);}elseif (flag1){sort(e 1, e 1 n, cmp1);int res 0, cur 1;while (cur n res T){ans;res e[cur].c;cur;}printf(%d\n, ans - 1);}else{sort(e 1, e 1 n, cmp2);for (int i 1; i n; i){int j i 1, res 0;while (j n res T){res abs(e[j].h - e[j-1].h);j;}ans max(ans, j - i 1);}printf(%d\n, ans - 1);}return 0;
} 正解 #include cstdio
#include cmath
#include cstring
#include iostream
#include algorithmusing namespace std;int n,T;
int f[60][60];struct node
{int c, h;
}e[60];bool cmp(node a, node b)
{return a.h b.h;
}int main()
{memset(f, 127 / 3, sizeof(f));scanf(%d, n);for (int i 1; i n; i)scanf(%d, e[i].c);for (int i 1; i n; i)scanf(%d, e[i].h);scanf(%d, T);sort(e 1, e 1 n, cmp);f[0][1] e[1].c;for (int i 0; i n; i)for (int j 1; j n; j)for (int k j 1; k n; k)f[i 1][k] min(f[i 1][k], f[i][j] e[k].h - e[j].h e[k].c);for (int i n; i 0; i--)for (int j 1; j n; j)if (f[i][j] T){printf(%d\n, i 1);return 0;}printf(0\n);return 0;
} 转载于:https://www.cnblogs.com/zbtrs/p/7763968.html
