OSU!

之前做过。

[春季测试 2023] 圣诞树

好题。因为三角形两边和大于第三边，所以路径不交叉一定比路径交叉优。那么考虑区间 DP。首先断环为链，设 \(dp_{l,r,0/1}\) 表示当前已经走完了区间 \([l,r]\)，当前在区间最左/右侧。同时记录 \(pre_{l,r,0/1}\) 表示对应状态的 \(dp\) 是从上一步的左/右侧转移过来的。输出直接递归或用栈就可以了。注意：由于坐标可以为负，所以一定注意边界条件。

code 
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
constexpr int N=1e3+10;
int n,s;
struct Node{
    double x,y;
    int id;
}node[N<<1];
double dp[N<<1][N<<1][2],ans;
int pre[N<<1][N<<1][2];
inline double dis(const Node &a,const Node &b){
    double x=a.x-b.x,y=a.y-b.y;
    return sqrt(x*x+y*y);
}
void print(int l,int r,int p){
    if(l==r){
        printf("%d ",node[l].id);
        return;
    }
    if(p){
        print(l,r-1,pre[l][r][p]);
        printf("%d ",node[r].id);
    }
    else{
        print(l+1,r,pre[l][r][p]);
        printf("%d ",node[l].id);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    node[s].y=-0x7fffffff;
    for(int i=1;i<=n;i++){
        cin>>node[i].x>>node[i].y;
        node[i].id=i;
        node[i+n]=node[i];
        if(node[i].y>node[s].y) s=i;
    }
    for(int i=1;i<=(n<<1);i++)
        for(int j=i;j<=(n<<1);j++)
            dp[i][j][0]=dp[i][j][1]=0x7fffffff;
    dp[s][s][0]=dp[s][s][1]=dp[s+n][s+n][0]=dp[s+n][s+n][1]=0;
    for(int len=2;len<=n;len++)
        for(int l=1,r=l+len-1;r<=(n<<1);l++,r++){
            //0 left ,1 right
            double a=dp[l+1][r][0]+dis(node[l],node[l+1]),b=dp[l+1][r][1]+dis(node[l],node[r]);
            if(a>b) dp[l][r][0]=b,pre[l][r][0]=1;
            else dp[l][r][0]=a,pre[l][r][0]=0;
            a=dp[l][r-1][1]+dis(node[r-1],node[r]),b=dp[l][r-1][0]+dis(node[l],node[r]);
            if(a>b) dp[l][r][1]=b,pre[l][r][1]=0;
            else dp[l][r][1]=a,pre[l][r][1]=1;
        }
    ans=0x7fffffff;
    for(int i=1;i<=n;i++)
        ans=min({ans,dp[i][i+n-1][0],dp[i][i+n-1][1]});
    for(int i=1;i<=n;i++){
        if(dp[i][i+n-1][0]==ans){
            print(i,i+n-1,0);
            return 0;
        }
        if(dp[i][i+n-1][1]==ans){
            print(i,i+n-1,1);
            return 0;
        }
    }
    return 0;
}

[JSOI2018] 潜入行动

树上背包。朴素的状态不足以表达信息时就考虑加状态。\(dp_{u,i,0/1,0/1}\) 表示以 \(u\) 为根的子树中，放了 \(i\) 个监视器，点 \(u\) 放/不放，点 \(u\) 是/否被覆盖。转移时涉及滚动数组，所以我们记 \(temp_{i,0/1,0/1}\) 表示当前的 \(dp_{u,i,0/1,0/1}\)。
转移有点麻烦：
\[dp_{u,i+j,0,0}=\sum temp_{i,0,0}\times dp_{v,j,0,1}\] \[dp_{u,i+j,1,0}=\sum temp_{i,1,0}\times dp_{v,j,0,0/1}\] \[dp_{u,i+j,0,1}=\sum temp_{i,0,0}\times dp_{v,j,1,1}+temp_{i,0,1}\times dp_{v,j,0/1,1}\] \[dp_{u,i+j,1,1}=\sum temp_{i,1,0}\times dp_{v,j,1,0/1}+temp_{i,1,1}\times dp_{v,j,0/1,0/1}\]

code 
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int mod=1e9+7,N=1e5+10;
struct modint{
    int val;
    modint(int val=0):val(val){}
    modint operator+(const modint &x)const{return modint((val+x.val)%mod);}
    modint &operator+=(const modint &x){val+=x.val;val%=mod;return *this;}
    modint operator*(const modint &x)const{return modint((ll)val*x.val%mod);}
};
vector<int> e[N];
int n,k,siz[N];
modint dp[N][110][2][2],temp[110][2][2];
void dfs(int u,int fa){
    dp[u][1][1][0]=dp[u][0][0][0]=1;
    siz[u]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int i=0;i<=k;i++){
            temp[i][0][0]=dp[u][i][0][0];
            temp[i][0][1]=dp[u][i][0][1];
            temp[i][1][0]=dp[u][i][1][0];
            temp[i][1][1]=dp[u][i][1][1];
            dp[u][i][0][0]=dp[u][i][0][1]=dp[u][i][1][0]=dp[u][i][1][1]=0;
        }
        for(int i=0;i<=min(siz[u],k);i++)
            for(int j=0;j<=min(siz[v],k-i);j++){
                dp[u][i+j][0][0]+=temp[i][0][0]*dp[v][j][0][1];
                dp[u][i+j][1][0]+=temp[i][1][0]*(dp[v][j][0][0]+dp[v][j][0][1]);
                dp[u][i+j][0][1]+=temp[i][0][0]*dp[v][j][1][1]+
                temp[i][0][1]*(dp[v][j][0][1]+dp[v][j][1][1]);
                dp[u][i+j][1][1]+=temp[i][1][0]*(dp[v][j][1][0]+dp[v][j][1][1])+
                temp[i][1][1]*(dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]);
            }
        siz[u]+=siz[v];
    }
}
int main(){
    read(n,k);
    for(int i=1,u,v;i<n;i++){
        read(u,v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",(dp[1][k][0][1]+dp[1][k][1][1]).val);
    return 0;
}

AT_dp_e Knapsack 2

背包变形。将 \(v\) 和 \(w\) 互换一下就行。

code 
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
#include<cstdio>
#include<cstring>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
template<typename T>
inline T Min(const T &a,const T &b){return a<b?a:b;}
constexpr int N=1e5+10;
typedef long long ll;
int n,W,w,v,sum;
ll dp[N];
int main(){
    read(n,W);
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        read(w,v);
        sum+=v;
        for(int j=sum;j>=v;j--)
            dp[j]=Min(dp[j],dp[j-v]+w);
    }
    for(int i=sum;i;i--)
        if(dp[i]<=W){
            printf("%d\n",i);
            return 0;
        }
    return 0;
}

AT_dp_j Sushi

\(dp_{i,j,k}\) 表示有 \(i\) 个装 \(1\) 个寿司，\(j\) 个装 \(2\) 个寿司和 \(k\) 个装 \(3\) 个寿司的盘子的期望次数。\(dp_{i,j,k}\) 为以下四项之和：
- \(\dfrac{n-(i+j+k)}{n}\times (dp_{i,j,k}+1)\)（空盘子）

  • \(\dfrac{i}{n}\times (dp_{i-1,j,k}+1)\)（放 \(1\) 个）

  • \(\dfrac{j}{n}\times (dp_{i+1,j-1,k}+1)\)（放 \(2\) 个）

  • \(\dfrac{k}{n}\times (dp_{i,j+1,k-1}+1)\)（放 \(3\) 个）

整理，得
\[dp_{i,j,k}=\frac{n}{i+j+k}+\frac{i\times dp_{i-1,j,k}}{i+j+k}+\frac{j\times dp_{i+1,j-1,k}}{i+j+k}+\frac{k\times dp_{i,j+1,k-1}}{i+j+k}\] 显然，应当按 \(k-j-i\) 顺序枚举以消除后效性。边界：\(dp_{0,0,0}=0\)。

code 
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
#include<cstdio>
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
constexpr int N=310;
int n,cnt[4];
double dp[N][N][N];
int main(){
    read(n);
    for(int i=1,a;i<=n;i++) read(a),++cnt[a];
    for(int k=0;k<=n;k++)
        for(int j=0;j<=n;j++)
            for(int i=0;i<=n;i++){
                if(i==j&&j==k&&k==0) continue;
                double inv=i+j+k;
                dp[i][j][k]=n/inv;
                if(i) dp[i][j][k]+=dp[i-1][j][k]*i/inv;
                if(j) dp[i][j][k]+=dp[i+1][j-1][k]*j/inv;
                if(k) dp[i][j][k]+=dp[i][j+1][k-1]*k/inv;
            }
    printf("%.10lf",dp[cnt[1]][cnt[2]][cnt[3]]);
    return 0;
}