AtCoder DP专题26道

如果全部掌握了DP应该算是小有所成了
一半是寒假写的，另一半算是暑假补作业。

A - Frog 1

B - Frog 2

C - Vacation

D - Knapsack 1

E - Knapsack 2

F - LCS

G - Longest Path

H - Grid 1

I - Coins

J - Sushi 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int cnt[10], a, n;
db dp[N][N][N];

db dfs(int a, int b, int c) {
   if(!a && !b && !c) return 0;
   if(dp[a][b][c]) return dp[a][b][c];
   db sum = a+b+c;
   db ans = 1.0*n / sum;
   if(a) ans += 1.0*a/sum * dfs(a-1, b, c);
   if(b) ans += 1.0*b/sum * dfs(a+1, b-1, c);
   if(c) ans += 1.0*c/sum * dfs(a, b+1, c-1);
   dp[a][b][c] = ans;
   return ans;
}

int main() {
   cin>>n;
   for1(i, n) {
      scanf("%d", &a);
      cnt[a]++;
   }
   db ans = dfs(cnt[1], cnt[2], cnt[3]);
   printf("%.8lf\n", ans);
   return 0;
}

K - Stones 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n, k, a[200], dp[N][2], p;

bool dfs(int num, int person) {
   if(dp[num][person]) return dp[num][person];
   int ans=0;
   for1(i, n) {
      if(a[i] <= num) ans |= !dfs(num - a[i], person^1);
   }
   dp[num][person] = ans;
   return ans;
}


int main() {
   scanf("%d %d", &n, &k);
   for1(i, n) scanf("%d", &a[i]);
   bool ans = dfs(k, 1);
   ans ? puts("First") : puts("Second");
   return 0;
}

L - Deque 

1
2
3
4
5
6
7
8
9
10
11
12
int n, a[N];
ll dp[N][N];

int main() {
   cin>>n;
   for1(i, n) scanf("%d", &a[i]);
   for(int i = n; i; --i)
      for(int j = i; j <= n; ++j) {
         dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]);
      }
   cout<<dp[1][n]<<endl;
}

M - Candies 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n, k, a[N];
ll dp[M], sum[M];

int main() {
   ms(dp, 0);
   dp[0] = 1;
   scanf("%d %d", &n, &k);
   for1(i, n) scanf("%d", &a[i]);
   for1(i, n) {
      ms(sum, 0);
      for(int j = k; j >= 0; --j) {
         int l = j+1, r = j + min(k - j, a[i]);
         if(l > r) continue;
         sum[l] = (sum[l] + dp[j]) % mod;
         sum[r+1] -= dp[j];
         if(sum[r+1] < 0) sum[r+1] += mod;
         // debug1 printf("%d %d %lld %lld\n", l, r, dp[j], sum[l]);
      }
      for1(j, k) {
         sum[j] = (sum[j] + sum[j-1]) % mod;
         dp[j] = (dp[j] + sum[j]) % mod;
      }
   }
   printf("%lld\n", dp[k]);
   return 0;
}

N - Slimes 石子合并问题

罗勇军区间DP讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll dp[N][N];
int n, a[N];

ll w(int i, int j) {
   ll ans = 0;
   for(int k = i; k <= j; ++k) ans+=a[k];
   return ans;
}

int main() {
   scanf("%d", &n);
   for1(i, n) scanf("%d", &a[i]);
   ms(dp, 0);
   for(int len = 2; len <= n; ++len) {
      for(int i=1; i+len-1 <= n; ++i) {
         int j = i+len-1;
         dp[i][j] = INF;
         for(int k = i; k < j; ++k) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + w(i, j));
            // debug1 printf("%d %d %lld %lld %lld %lld\n", i, j, dp[i][j], dp[i][k], dp[k+1][j], w(i, j));
         }
      }
   }
   cout<<dp[1][n]<<endl;
}

O - Matching 状压dp

罗勇军状压dp讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int n, mp[N][N];
ll dp[M];

int main() {
   cin>>n;
   for0(i, n) for0(j, n) {
      scanf("%d", &mp[i][j]);
   }
   dp[0] = 1;
   for0(i, (1<<n)) {
      int cnt = 0;
      for0(j, n) {
         if((i >> j) & 1) {
            cnt++; // 记录已经匹配完成的人数
         }
      }
      cnt--;
      for0(j, n) {
         if(mp[cnt][j] && (i & (1<<j))) {
            dp[i] = (dp[(1<<j)^i] + dp[i]) % mod;
            // debug1 printf("%d %d %d %d\n", i, j, mp[cnt][j], cnt);
         }
      }
   }
   cout<<dp[(1<<n)-1]<<endl;
}

P - Independent Set 树形dp

思路
树形dp的思想就是从下向上的dp，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n, tot, head[N], ver[N<<2], nex[N<<2];
ll dp[N][2];

void add(int x, int y) {
   ver[++tot] = y;
   nex[tot] = head[x];
   head[x] = tot;
}

void dfs(int x, int fa) {
   ll a = 1, b = 1;
   if(nex[head[x]] == 0 && ver[head[x]] == fa) {
      dp[x][0] = dp[x][1] = 1;
      return;
   }
   for(int i = head[x]; i; i = nex[i]) {
      int y = ver[i];
      if(y == fa) continue;
      dfs(y, x);
      a = (a * ((dp[y][0] + dp[y][1]) % mod)) % mod;
      b = (b * dp[y][0]) % mod;
   }
   dp[x][0] = a, dp[x][1] = b;
}

int main() {
   cin>>n;
   for0(i, n-1) {
      int x, y;
      scanf("%d %d", &x, &y);
      add(x, y), add(y, x);
   }
   dfs(1, 0);
   cout << (dp[1][0] + dp[1][1]) % mod << endl;
   return 0;
}

Q - Flowers LIS思想 + 线段树维护

题意
每支花有高度值和价值两个整数，要求从1~n选出一段，使得高度呈单调递增，同时价值的总和最大。求最大价值。

思路
根据最长上升子序列的思想很容易想到O(n^2)的做法，但是会T。我们发现对于每一支花，他的dp价值就等于前面比他低的最高的花的dp值与其相加。使用线段树进行维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define mid ((l+r)>>1)

struct node {
    int id,h;
    ll s;
}arr[N];
ll dp[N],maxx[N<<2];
void up(int rt) {
    maxx[rt] = max(maxx[rt<<1],maxx[rt<<1|1]);
}
void update(int rt,int l,int r,int x,ll v)
{
    if(l==r)
    {
        maxx[rt] = max(maxx[rt],v);
        return ;
    }
    if(x<=mid) update(rt<<1,l,mid,x,v);
    else update(rt<<1|1,mid+1,r,x,v);
    up(rt);
}
ll query(int rt,int l,int r,int x,int y)
{
    if(x>r||y<l) return 0;
    if(x<=l&&r<=y)
    {
        return maxx[rt];
    }
    if(x>mid) return query(rt<<1|1,mid+1,r,x,y);
    else if(y<=mid) return query(rt<<1,l,mid,x,y);
    else return max(query(rt<<1,l,mid,x,y),query(rt<<1|1,mid+1,r,x,y));
}

int main() {
    int n;
    ll ans = 0;
    scanf("%d", &n);
    for(int i = 1;i<=n;++i) scanf("%d",&arr[i].h);
    for(int i = 1;i<=n;++i) scanf("%lld",&arr[i].s),arr[i].id = i;
    for(int i = 1;i<=n;++i)
    {
        ll tmp = 0;
        if(arr[i].h>1)  tmp = query(1,1,n,1,arr[i].h-1);
        update(1,1,n,arr[i].h,tmp+arr[i].s);
    }
    printf("%lld\n",maxx[1]);
    return 0;
}

R - Walk 倍增floyd???

题意
一个有向图，起点和终点任意问有多少种长度为k的不同路线；

思路
矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ll n, k;
struct node {
   ll mp[N][N];
   node() { ms(mp, 0);}
};


node matmul(node a, node b) {
   node ans;
   for1(i, n) for1(j, n) for1(k, n) {
      ans.mp[i][j] = (ans.mp[i][j] + (a.mp[i][k] * b.mp[k][j]) % mod) % mod;
   }
   return ans;
}

node matpow(node a, ll b) {
   node ans;
   for1(i, n) ans.mp[i][i] = 1;
   while(b) {
      if(b & 1) ans = matmul(ans, a);
      a = matmul(a, a);
      b >>= 1;
   }
   return ans;
}

int main() {
   node a;
   cin >> n >> k;
   for1(i, n) for1(j, n) {
      scanf("%lld", &a.mp[i][j]);
   }
   node res = matpow(a, k);
   ll ans = 0;
   for1(i, n) for1(j, n) {
      ans = (ans + res.mp[i][j]) % mod;
   }
   printf("%lld\n", ans);
   return 0;
}

S - Digit Sum 数位dp

题意
数位dp的入门题目，给出范围1~r，求出各位相加的和模一个数为0的数有多少个。

思路
基于“试填”的思想从高位到低位递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll dp[N][M][2];
string str;
int a[N], d, len;

int dfs(int k, int now, int lim) {
   if(dp[k][now][lim] >= 0) return dp[k][now][lim];
   if(k == len) return dp[k][now][lim] = (now == 0);
   ll sum = 0;
   int up = lim ? a[k] : 9;
   for0(i, up+1) {
      sum += dfs(k+1, (now+i) % d, lim && i==up);
      sum %= mod;
   }
   return dp[k][now][lim] = sum;
}

int main() {
   ms(dp, -1);
   cin>>str>>d;
   len = str.size();
   for0(i, len) a[i] = str[i] - '0';
   ll ans = (dfs(0, 0, 1) - 1 + mod) % mod;
   cout<<ans<<endl;
   return 0;
}

T - Permutation 求出递推公式

题意
给出一个全排列数组的长度和相邻数之间的关系，求满足条件的数组有多少个。

思路
设dp[i][j]表示1~i之间的全排列中第i位上的数字是j的情况有多少种。

  1. 当第i个关系为 < 时，有dp[i][1]=0; dp[i][2]=dp[i-1][1]+dp[i]1; dp[i][3]=dp[i-1][2]+dp[i][2];……
  2. 当第i个关系为 < 时，有dp[i][i]=0; dp[i][i-1]=dp[i][i]+dp[i-1][i-1];……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll dp[N][N], n, ans;
char chr[N];

int main() {
   cin>>n;
   scanf("%s", chr+1);
   dp[1][1] = 1;
   for(int i = 2; i <= n; ++i) {
      if(chr[i-1] == '<') {
         dp[i][1] = 0;
         for(int j = 2; j <= i; ++j) {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]) % mod;
         }
      } else {
         dp[i][i] = 0;
         for(int j = i-1; j; --j) {
               dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % mod;
         }
      }
   }
   for1(i, n) {
      ans = (ans + dp[n][i]) % mod;
   }
   cout<<ans<<endl;
}

U - Grouping 状压DP枚举子集

枚举子集的公式推导
题意
给出n个兔子，任意分组，得分为分到一组的匹配贡献值的和，求最大的得分；

思路
根据给出的数据量最多16个兔子，刚好适合利用状压dp枚举1 ~ (1 << n)的状态，并且枚举子集获取状态i的情况下的最大得分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n, a[N][N], con[N];
ll ans, dp[M], tmp[M];

int main() {
   scanf("%d", &n);
   for0(i, n) for0(j, n) scanf("%d", &a[i][j]);

   for0(now, (1<<n)) {
      int cnt = 0;
      for0(i, 16)
         if(now & (1<<i)) {
            con[cnt++] = i;
         }
      ll sum = 0;
      for0(i, cnt) for(int j = i + 1; j < cnt; ++j) {
         sum += a[con[i]][con[j]];
      }
      dp[now] = tmp[now] = sum;
   }
   // 枚举状态now的全部子集取最大值，不知道公式是怎么来的。
   for0(now, (1<<n)) for(int last = now; last; last = (last-1) & now) {
      dp[now] = max(dp[now], dp[now ^ last] + tmp[last]);
   }

   cout<<dp[(1<<n) - 1]<<endl;
   return 0;
}

V - Subtree

W - Intervals \

题意
给出一个长度为N的字符串容器，每个位置只能填0/1。接下来是M个条件，在li~ri之间如果存在1，那么就获得ai分（若第i个位置为1，那么得到包括该点所有区间的分数）。求可以获得的最大分数。

思路
按照右端点进行排序，可以遍历覆盖该点的所有区间。tag[i]表示该点为1时的得分和，sum[i]表示该点为1时的最大值。使用线段树进行转移。
转移过程：

  1. 维护之前使用根节点（当前最大分值）对当前点进行维护。
  2. 将相同右端点的区间统一维护；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int n, m;
ll sum[N<<2], tag[N<<2];
struct node {
   int l, r, a;
}b[N];

bool cmp(node x, node y) {
   return x.r < y.r;
}

void add(int rt, int L, int R, int x, int y, ll val) {
   if(x <= L && y >= R) {
      sum[rt] += val, tag[rt] += val;
      return;
   }
   int mid = (L + R) >> 1;
   if(x <= mid) add(rt<<1, L, mid, x, y, val);
   if(y > mid) add(rt << 1 | 1, mid+1, R, x, y, val);
   sum[rt] = max(sum[rt<<1], sum[rt<<1|1]) + tag[rt];
}

int main() {
   scanf("%d %d", &n, &m);
   for1(i, m) {
      scanf("%d %d %d", &b[i].l, &b[i].r, &b[i].a);   
   }
   sort(b+1, b+1+m, cmp);
   int idx = 1;
   for1(i, n) {
      add(1, 1, n, i, i, sum[1]);
      while(b[idx].r == i) {
         // debug1 printf("%d %d %d\n", b[idx].l, b[idx].r, b[i].a);
         add(1, 1, n, b[idx].l, i, b[idx].a);
         idx++;
      }
   }
   cout << max(sum[1], (ll)0) << endl;
   return 0;
}

X - Tower 转化为背包问题

题意
堆石头，每块石头有各自的重量，承载能力，价值。求可以堆出来的最大价值。

思路
从上往下堆更加容易，但是要提前排好序。可以发现当需要选择接下来堆两块石头i和j的顺序时，可以贪心的思考。比如i在j上面，当前的重量是w，那么si < w + wj, sj > w + wi。联立两个式子可以得到si + wi < sj + wj。排序后问题转化为01背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct node {
   int w, v, s;
}a[N];
ll n, dp[M], ans;

bool cmp(node a, node b) {
   return a.w+a.s < b.w+b.s;
}

int main() {
   cin>>n;
   for1(i, n) scanf("%d %d %d", &a[i].w, &a[i].s, &a[i].v);
   sort(a+1, a+1+n, cmp);

   for1(i, n) for(int j = M-10; j >= a[i].w; --j) {
      if(a[i].s + a[i].w >= j) dp[j] = max(dp[j], dp[j-a[i].w] + a[i].v);
   }

   for1(i, M) ans = max(ans, dp[i]);
   cout<<ans<<endl;
}

Y - Grid 2

Z - Frog 3

一只GIS专业的ACMer