Eternity

Until The End

2022.07.04练习题

发表于 更新于 分类于
本文字数： 5.1k 阅读时长 ≈ 5 分钟

考场得分： $0+0+33pts+10pts=43pts$

现在得分： $9pts+0+100pts+100pts=209pts$

T1 Express

T2 Tree

T3 frenzy

背包裸题，但是还是寄了。

令 $dp[i]$ 表示得分为 $i$ 需要的最短时间，转移方程：

$dp[i]=\min\{dp[i],dp[i-p[j]]+t[j]\},i\in[1,k],j\in[1,n],i-p[j]\ge a[j]$

存在有 $p[i],a[i]\ge k$ 的情况，所以初始化请尽可能大。

时间复杂度 $\mathcal O(nk)$

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=10001;
const long long INF=1e18;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,n,k;
struct Fish
{
    ll a,p,t;
}val[MAXN];
ll dp[MAXN*10],mxP;
inline void init()
{
    mxP=0;
    read(n,k);
    for(int i=1;i<MAXN;++i) dp[i]=INF;
    for(int i=1;i<=n;++i) read(val[i].a,val[i].p,val[i].t);
    for(int i=1;i<=n;++i) checkMax(mxP,val[i].p);
}
inline ll dpCnt(int n,int x)
{
    dp[0]=0;
    for(int i=1;i<x+mxP;++i)
        for(int j=1;j<=n;++j)
            if(val[j].a<=i-val[j].p)
                dp[i]=min(dp[i],dp[i-val[j].p]+val[j].t);
    ll ans=INF;
    for(int i=x;i<x+mxP;++i) checkMin(ans,dp[i]);
    return ans;
}
int main()
{
    // freopen("frenzy.in","r",stdin);
    // freopen("frenzy.out","w",stdout);
    read(Test);
    while(Test--)
    {
        init();
        printf("%lld\n",dpCnt(n,k));
    }
    return 0;
}
/*
3
2 10
0 2 3
5 3 5
2 9
0 2 3
5 3 5
2 1
1 5 6
2 7 8
*/

T4 castle

状压裸题，但是还是寄了。

其实应该要想到的，毕竟一个 $n\le 17$ 就摆在那儿，可能是因为在做前两道题，所以就糊了一个 $Dijkstra$ 过去，还骗了 $10pts$ 就离谱。

以 $dp[s][i]$ 表示当前状态为 $s$ ，当前位置为 $i$ 的最长路径。（这里的 $i$ 应该是 $i\in [0,n-1]$ 的，方便于状态压缩的表示，表示类似于哈密顿路径那道题）

为什么是最长路径？在最后的答案，我们用 $cnt$ 表示经过路径的怪物和，用 $dp[s_0][T]$ 表示路径长度，则有 $ans=\min\{\frac{cnt}{dp[s_0][T]}\}$ ，那么，在 $cnt$ 相等的情况下，则 $dp[s_0][T]$ 越大， $ans$ 越小。（这就是为什么我第二个样例一直调不出来的原因）

转移方程：

$dp[s][ed]=\min\{dp[s][st]+path[st][ed]\},c(st,ed)\in E,st,ed\in s$

即可，我因为一直调不出来，就把重边记录了最大值和最小值，然后建反边跑了两次，实际上是不需要的。

时间复杂度 $\mathcal O(n^22^n)$ 。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=21;
const int MAXM=520;
const int MAXS=(1<<18)+1;
const int INF=0x3f3f3f3f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,val[MAXN],path[3][MAXN][MAXN];
int dp[3][MAXS][MAXN];
double ans=INF;
inline void dpSP(int op,int St,int Ed)
{
    for(int s=0;s<(1<<N);++s)
        for(int st=0;st<N;++st)
            if((s>>st)&1)
                for(int ed=0;ed<N;++ed)
                    if(((s>>ed)&1)&&path[op][st][ed]!=-1&&dp[op][s-(1<<ed)][st]!=-1)
                        dp[op][s][ed]=max(dp[op][s][ed],dp[op][s-(1<<ed)][st]+path[op][st][ed]);
    for(int s=0;s<(1<<N);++s)
        if(((s>>St)&1)&&((s>>Ed)&1)&&dp[op][s][Ed]>0)
        {
            int cnt=0;
            for(int i=0;i<N;++i) if((s>>i)&1) cnt+=val[i];
            double res=(cnt*1.0)/(dp[op][s][Ed]*1.0);
            checkMin(ans,res);
        }
    return ;
}
int main()
{
    // freopen("castle.in","r",stdin);
    // freopen("castle.out","w",stdout);
    read(N,M);
    for(int i=0;i<N;++i) read(val[i]);
    for(int op=0;op<=1;++op)
        for(int i=0;i<N;++i)
        {
            for(int j=0;j<N;++j)
                path[op][i][j]=-1;
            path[op][i][i]=0;
        }
    for(int i=1,u,v,w;i<=M;++i)
    {
        read(u,v,w);
        checkMin(path[0][u-1][v-1],w);
        checkMax(path[1][v-1][u-1],w);
    }
    int S,T;
    read(S,T);
    --S;--T;
    for(int op=0;op<=1;++op)
        for(int s=0;s<(1<<N);++s)
            for(int i=0;i<N;++i)
                dp[op][s][i]=-1;
    dp[0][(1<<S)][S]=0;
    dp[1][(1<<T)][T]=0;
    dpSP(0,S,T);
    dpSP(1,T,S);
    printf("%.3lf",ans);
    return 0;
}
/*
7 9
3 0 6 9 1 0 10
1 6 5
6 2 3
3 2 2
2 4 4
4 3 9
3 5 1
4 5 3
5 6 2
5 1 7
2 6
*/
相关文章