2024年5月21日

A luoguP3030

考虑DP

状态 （i, sum, data）表示已经放了 \(i\) 个砖块, 总和为 \(sum\) 是的最小花钱。

转移 : 枚举第 \(i\) 个选多少。

时间复杂度 \(O(n\sqrt{m} \cdot m)\)

#include<bits/stdc++.h>

using namespace std;

const int N = 15, M = 10005;
const long long INF = 1e18;

int n, m, a[N];
long long dp[N][M];

int main(){
  freopen("tilechng.in", "r", stdin);
  freopen("tilechng.out", "w", stdout);
  cin >> n >> m;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for(int i = 0; i <= n; ++i){
    for(int j = 0; j <= m; ++j){
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= 100; ++j){
      for(int k = j * j; k <= m; ++k){
        dp[i][k] = min(dp[i][k], dp[i - 1][k - j * j] + 1ll * abs(a[i] - j) * abs(a[i] - j));
      }
    }
  }
  cout << (dp[n][m] == INF ? -1 : dp[n][m]);
  return 0;
}

B luoguP3029

对位置从小到大排序, 双指针不断的把元素删除, 压入元素。

时间复杂度 \(O(n \log n)\)

#include<bits/stdc++.h>

using namespace std;

const int N = 50005;

struct Node{
  int x, id;
}a[N];

int n, last, tot, sum, ans = 2e9, cnt[N];
vector<int>v;

int main(){
  freopen("lineup.in", "r", stdin);
  freopen("lineup.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i].x >> a[i].id;
    v.push_back(a[i].id);
  }
  sort(a + 1, a + n + 1, [](const Node &i, const Node &j){  return i.x < j.x;});
  sort(v.begin(), v.end());
  last = -1;
  for(auto x : v){
    if(last != x){
      last = x;
      tot++;
    }
  }
  for(int i = 1; i <= n; ++i){
    a[i].id = lower_bound(v.begin(), v.end(), a[i].id) - v.begin();
  }
  for(int l = 1, r = 1; r <= n; ++r){
    sum += !cnt[a[r].id];
    cnt[a[r].id]++;
    for(; l <= r && cnt[a[l].id] >= 2; cnt[a[l].id]--, l++){
    }
    if(sum == tot){
      ans = min(ans, a[r].x - a[l].x);
    }
  }
  cout << ans;
  return 0;
}

C luoguP2176

搜出一条最段路, 枚举每一条在最短路上的边, 取出把草放在上面之后的最短路。

最短路最多只有 \(n - 1\) 条边。

时间复杂度 \(O(n^3)\)

#include<bits/stdc++.h>

using namespace std;

const int N = 105, M = 10005;

struct Node{
  int a, b;
}pre[N];

struct cmp{
  bool operator()(const Node &i, const Node &j){
    return i.b > j.b;
  }
};

int n, m, vis[N], dist[N], maxx, id, u, v, w[M], ans, op;
vector<Node>g[N];
vector<int>e;
priority_queue<Node, vector<Node>, cmp>pq;

void dij(int s){
  for(int i = 1; i <= n; ++i){
    vis[i] = 0, dist[i] = 1e9;
  }
  dist[s] = 0;
  for(int i = 1; i < n; ++i){
    maxx = 1e9 + 1, id = -1;
    for(int j = 1; j <= n; ++j){
      if(maxx > dist[j] && !vis[j]){
        maxx = dist[j];
        id = j;
      }
    }
    if(id == -1){
      continue;
    }
    vis[id] = 1;
    //cout << maxx <<' ' << id <<'\n';
    for(auto [u, wd] : g[id]){
      if(dist[u] > dist[id] + w[wd]){
        dist[u] = dist[id] + w[wd];
        pre[u] = {id, wd};
      }
    }
  }
}

void DFS(int x){
  if(!x){
    return;
  }
  DFS(pre[x].a);
  if(pre[x].a){
    e.push_back(pre[x].b);
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  freopen("rblock.in", "r", stdin);
  freopen("rblock.out", "w", stdout);
  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    cin >> u >> v >> w[i];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  dij(1);
  op = dist[n];
  DFS(n);
  for(auto x : e){
    w[x] *= 2;
    dij(1);
    ans = max(ans, dist[n] - op);
    w[x] /= 2;
  }
  cout << ans;
  return 0;
}