danihao123's Blog

付公主有一个大小为\(10^5\)的背包。然你有\(n\)种类型的物品，其中第\(i\)种体积为\(V_i\)（是正整数），数量有\(10^5\)件。然后给出一正整数\(m\)，对任意\(i=1\ldots m\)求出包里恰好装了\(i\)体积的物品的方案数，答案对\(998244353\)取模。

\(1\leq n\leq 10^5, m\leq 10^5, V_i\leq m\)。

啊啊啊只会做水题了……

很显然是最小割吧……长得很像最大权闭合子图，但又不一样的。

那么就把最大权闭合子图中的无穷边（我称之为违约边）的费用改成租用的费用。这样一来，如果选了计划（不割计划）还不购买机器（割去机器），那就只能支付租金了（割违约边）。

这其实也算是一种套路了吧？觉得以前见过很多次但是有很多叫法……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 200005;
const int maxm = 2000005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
  return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
  add_edge(u, v, f);
  add_edge(v, u, 0);
}
 
int d[maxn];
int s, t, tot;
inline bool bfs() {
  static bool vis[maxn];
  std::fill(vis, vis + 1 + tot, false);
  std::fill(d, d + 1 + tot, 0);
  std::queue<int> Q;
  Q.push(s); vis[s] = true; d[s] = 1;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ans = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i];
    int f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ans += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ans;
}
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

int main() {
  int n, m; scanf("%d%d", &n, &m);
  s = 0; t = tot = n + m + 1;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    int w, p; scanf("%d%d", &w, &p);
    ins_edge(s, i, w); ans += w;
    for(int j = 1; j <= p; j ++) {
      int id, co; scanf("%d%d", &id, &co);
      ins_edge(i, id + n, co);
    }
  }
  for(int i = n + 1; i <= n + m; i ++) {
    int co; scanf("%d", &co);
    ins_edge(i, t, co);
  }
  printf("%d\n", ans - dinic());
  return 0;
}

DP神题……

第一眼都能看出来是DP，然后大约构思就出来了，但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态，但是注意[tex]A[i]=B[j][/tex]（字符数组细节此处未予考虑）的情况和整体情况要独立对待，否则这题只能233

然后下面就不难想了。但是注意直接开数组会233，要开滚动数组防MLE。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}

倍增LCA经典题……

这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……

注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！

代码：