8-3 小A的最短路
分析：不坐缆车时，就是LCA求树上两点距离的板子题，多了一个缆车(U, V)，那么不坐时，距离还是原来的距离；坐时，要么先从x到U，在从V到y，要么先从x到V，再从U到y，这几种情况取个最优即可！
比板子题也就多了几行。。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 3e5+5;
struct edge{
int from, to, next;
}e[maxn*2];
int n, head[maxn], tot, U, V, q;
int lg[maxn], fa[maxn], dp[maxn][25], depth[maxn];
inline int Min(int a, int b){
return a<b?a:b;
}
inline int LCA(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
while (depth[u] > depth[v]) u = dp[u][lg[depth[u]-depth[v]]-1];
if (u==v) return u;
for (int k=lg[depth[u]]-1; k>=0; k--) if (dp[u][k]!=dp[v][k])
u = dp[u][k], v = dp[v][k];
return dp[u][0];
}
inline int dist(int u, int v){
int tmp = LCA(u, v);
return depth[u]+depth[v]-2*depth[tmp];
}
void dfs(int u, int v){
fa[u] = v;
depth[u] = depth[v] + 1;
for (int i=head[u]; i; i=e[i].next) if (!depth[e[i].to]){
dfs(e[i].to, u);
}
return;
}
inline void init(){
for (int i=1; i<=n; i++)
lg[i] = lg[i-1] + (1<<lg[i-1]==i);
dfs(1, 0);
for (int i=1; i<=n; i++) dp[i][0] = fa[i];
for (int k=1; k<=lg[n]-1; k++) for (int i=1; i<=n; i++)
dp[i][k] = dp[dp[i][k-1]][k-1];
return;
}
inline void add(int from, int to){
tot++;
e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
head[from] = tot;
return;
}
inline int read(){
int x=0; char ch = getchar();
while (ch<'0' || ch>'9') ch = getchar();
while (ch>='0' && ch<='9'){
x = x*10 + ch-'0';
ch = getchar();
}
return x;
}
int main(){
int from, to;
n = read();
for (int i=1; i<n; i++){
from = read(), to = read();
add(from, to); add(to, from);
}
init();
U = read(), V = read(), q = read();
for (int i=1; i<=q; i++){
from = read(), to = read();
printf ("%d\n", Min(dist(from, to), Min(dist(from, V)+dist(U, to), dist(from, U)+dist(V, to))));
}
return 0;
}8-3 购物
二维dp，令dp[i][j]表示前i天共买了j块糖果的最小花费，状态转移方程也很简单：
dp[i][j] = min(dp[i][j], dp[i-1][j-k]+c[i][k])
k表示第i天买k块糖果，这里对原数组c进行处理，先对第i天的糖果价钱排序，然后再求前缀和，再加上kk，使得c[i][k]表示第i天买k块糖果时的价钱。
然后，这题的限制条件挺多的，首先我们每天都只吃1块糖果，所以对于任意i,j都要满足j>=i，同时j还要满足j<=im，即前i天最多买i*m块糖，以及j<=n，n天下来只需要买n块糖即可。k满足的条件有：k<=m, j-k>=i-1，即第i天买了k块，前i-1天买了j-k块，同时j-k>=i-1，这个条件很重要，这样就能保证之前的i-1天都能满足j>=i这个条件！
那么最终的答案就是dp[n][n]了。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m;
int c[305][305];
ll dp[305][305];
int main(){
scanf ("%d %d", &n, &m);
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++) scanf ("%d", &c[i][j]);
sort (c[i]+1, c[i]+m+1);
for (int j=1; j<=m; j++) c[i][j] += c[i][j-1];
for (int j=1; j<=m; j++) c[i][j] += j*j;
}
for (int j=1; j<=m; j++) dp[1][j] = c[1][j];
for (int i=2; i<=n; i++){
for (int j=i; j<=n && j<=i*m; j++){
for (int k=0; k<=m && j-k>=i-1; k++){
if (dp[i][j]==0) dp[i][j] = dp[i-1][j-k]+c[i][k];
else dp[i][j] = min(dp[i][j], dp[i-1][j-k]+c[i][k]);
}
}
}
printf ("%lld", dp[n][n]);
return 0;
}8-6 追债之旅
求最短路，在原有边权的基础上，新加了一个对步数的权值和限制，要求总权值最小。
Dij做法。
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1005, maxm = 100005;
struct edge{
int from, to, next;
int val;
}e[maxm*2];
int n, m, k, tot;
int head[maxn], dist[maxn], days[maxn];
int days_cost[15];
struct node{
int pos;
int val;
int days;
friend bool operator < (const struct node &a, const struct node &b){
return a.val+days_cost[a.days] > b.val+days_cost[b.days];
}
}tmp;
priority_queue<struct node> q;
inline void add(int from, int to, int value){
tot++;
e[tot].from = from, e[tot].to = to, e[tot].val = value, e[tot].next = head[from];
head[from] = tot;
}
int main(){
int u, v, w;
scanf ("%d %d %d", &n, &m, &k);
for (int i=1; i<=m; i++){
scanf ("%d %d %d", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
for (int i=1; i<=k; i++){
scanf ("%d", days_cost+i);
days_cost[i] += days_cost[i-1];
}
for (int i=1; i<=n; i++) dist[i] = 999999999;
dist[1] = 0; q.push(node{1, 0, 0});
while (!q.empty()){
tmp = q.top(); q.pop();
for (int i=head[tmp.pos]; i; i=e[i].next){
if (e[i].to==1) continue;
if (tmp.days>=k) continue;
if (days[e[i].to]==0){
days[e[i].to] = tmp.days + 1;
dist[e[i].to] = tmp.val + e[i].val;
q.push(node{e[i].to, dist[e[i].to], days[e[i].to]});
continue;
}
if (dist[tmp.pos]+e[i].val+days_cost[tmp.days+1] < dist[e[i].to]+days_cost[days[e[i].to]]){
days[e[i].to] = tmp.days + 1;
dist[e[i].to] = tmp.val + e[i].val;
q.push(node{e[i].to, dist[e[i].to], days[e[i].to]});
continue;
}
}
}
if (dist[n]!=999999999) printf ("%d", dist[n]+days_cost[days[n]]);
else puts("-1");
return 0;
}题意看题，，其实答案就是点集s中，距离最大的两个点的距离的一半，向上取整，其中一个点一定是深度最大的那个点，剩下一个点枚举点集s用LCA求最大距离。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 3e5+5, inf = 3e5+5;
struct edge
{
int from, to, next;
}e[maxn*2];
int n, tot, q, s;
int head[maxn], depth[maxn], fa[maxn], lg[maxn], dp[maxn][25];
int nums[1000005];
inline int LCA(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
while (depth[u] > depth[v]) u = dp[u][lg[depth[u]-depth[v]]-1];
if (u==v) return u;
for (int k=lg[depth[u]]-1; k>=0; k--) if (dp[u][k]!=dp[v][k])
u = dp[u][k], v = dp[v][k];
return dp[u][0];
}
void dfs(int u, int v){
depth[u] = depth[v] + 1;
dp[u][0] = v;
for (int i=head[u]; i; i=e[i].next) if (!depth[e[i].to]){
dfs(e[i].to, u);
}
return;
}
void init(){
for (int i=1; i<=n; i++)
lg[i] = lg[i-1] + (1<<lg[i-1]==i);
dfs(1, 0);
for (int k=1; k<=lg[n]-1; k++) for (int i=1; i<=n; i++)
dp[i][k] = dp[dp[i][k-1]][k-1];
}
inline void add(int from, int to){
tot++;
e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
head[from] = tot;
return;
}
int main(){
int from, to;
scanf ("%d", &n);
for (int i=1; i<n; i++){
scanf ("%d %d", &from, &to);
add(from, to); add(to, from);
}
init();
scanf ("%d", &q);
for (int i=1; i<=q; i++){
scanf ("%d", &s);
for (int j=1; j<=s; j++) scanf ("%d", nums+j);
if (s==1){
printf ("0\n");
continue;
}
int maxx = 0, flag, ans = 0;
for (int j=1; j<=s; j++) if (depth[nums[j]]>maxx){
maxx = depth[nums[j]];
flag = nums[j];
}
for (int j=1; j<=s; j++) if (nums[j]!=flag){
ans = max(ans, depth[nums[j]]+maxx-2*depth[LCA(flag, nums[j])]);
}
printf ("%d\n", ans/2+(ans%2));
}
return 0;
}
0 条评论