选取的做题记录

7/8

luoguP1417 烹调方案

跟某陈姓聚聚在一次模拟赛中的签到题codeforces有几分神似,不过据 机房大佬的博客的说法是这个题的分数可能会被减为负数,所以需要排序之后加一个01背包

然后,排序的部分,比较得到的是两个题目之间的局部最优,至于为什么局部最优排序之后可以得到全局最优,我说不清,可能跟国王游戏有点类似吧…(然而我自己都没有写过)(是机房大佬的说法啦……)

1
2
3
4
bool mmp(node x,node y)
{
return (x.v*x.t+y.v*(x.t+y.t))<(y.v*y.t+x.v*(x.t+y.t));
}

以上是化简前的,我自己程序里面的是化简后的,在下面给出

1
2
3
4
bool operator < (const node &x)const
{
return b*x.c>c*x.b;
}

然后后面直接加01背包就好了…贼水(就算是这样我还是看了原来模拟赛的排序代码,交了七八遍才好

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
#include <bits/stdc++.h>
#define N 10000000+1000
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int a,b,c;
bool operator < (const node &x)const
{
return b*x.c>c*x.b;
}
}q[N];
int T,n,f[N],ans;
signed main()
{
T=read(),n=read();
for(int i=1;i<=n;i++)q[i].a=read();
for(int i=1;i<=n;i++)q[i].b=read();
for(int i=1;i<=n;i++)q[i].c=read();
sort(q+1,q+1+n);
for(int i=1;i<=n;i++)
{
for(int j=T;j>=q[i].c;j--)
{
f[j]=max(f[j],f[j-q[i].c]+(q[i].a-q[i].b*j));
ans=max(f[j],ans);
}
}
printf("%lld",ans);
return 0;
}

luoguP1282多米诺骨牌

看到是蓝题dp就方了…然后…偷偷地跑去看了机房大佬的博客……

看了博客之后差不多懂了一点?(然而以后还要巩固啊)

可以把问题转化成类似于01背包的dp(感觉好像不是…机房大佬说是的…可以看作背包吧…)

按照博客中的写法,背包的容量维护的应该是上一行的数减下一行的数的差值的和

以下把上一行的数看作a[i],下一行的数看作b[i],我们记录每一个a[i]-b[i],把这个差值当作它的费用

再用一个dp的二维数组表示前i个数差值的和为j的最小交换次数,这里最小交换次数就是我们最终要求的价值

转移方程如下

1
2
dp[i][j]=min(dp[i-1][j-_minus[i]],dp[i-1][j+_minus[i]]+1)
//如果要翻转,只要把-_minus[i]改为+_minus[i]就行了,按背包理解是这样

注意数组第二维可能是负数,所以每个j在写的时候加一个N就行了

枚举j的时候从-N到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
#include <bits/stdc++.h>
#define N 10000
#define inf 2147483647
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,a[N],b[N],_minus[N],dp[2][N*3];//dp[i][j]:表示前i个数和为j的最小交换次数
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read(),b[i]=read();
_minus[i]=a[i]-b[i];
}
for(int i=0;i<=1;i++)
{
for(int j=-N;j<=N;j++)
{
dp[i][j+N]=inf;
}
}
dp[0][N]=0;
for(int i=1;i<=n;i++)
{
for(int j=-N;j<=N;j++)
{
dp[(i&1)][j+N]=min(dp[((i-1)&1)][j-_minus[i]+N],dp[((i-1)&1)][j+_minus[i]+N]+1);
}
}
for(int i=0;i<=N;i++)
{
int ans=min(dp[(n&1)][i+N],dp[(n&1)][-i+N]);
if(ans!=inf){printf("%lld",ans);break;}
}
return 0;
}

luoguP1736创意吃鱼法

这个题看了大半天之后觉得跟最大正方形在题目形式上有那么几分相像,然而…就停留在这里了…….后面先是写了一个24分的暴力(说好的三十分因为加了两个数据点…555QwQ毒瘤你谷人QwQ)然后又打了个假dp,理论上一分混不到,最后竟然混了24分(并没有什么区别desu)

最大正方形那一题当时我是打了一个暴力a了,然后为了学dp抄题解打了一个dp,在那个题

1
dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;

因为dp表达的是以(i,j)为正方形右下角时的正方形最大边长,此dp值诚然可以受到三个状态上的转移,一个是自己左上角,一个是正上方,还有一个是自己左边

以此类推到本题(其实是说不出来为什么两个题有关联……)

以(i,j)为正方形右下角或左下角的答案也是受到三个方向上的影响,然而这里左边和上边记录的就不在是最大边长什么的了,而是变成了左边和右边到上一个出现1的地方之间的0的个数,假设左边记录的值用preleft,上边记录的值为preup,转移方程就是

1
f[i][j]=min(f[i-1][j-1]+1,min(preleft[i][j-1],preup[i-1][j])+1);

据其他博客上的题解所说,是可以画图得到的(然而我怎么就没有画出来呢??!!)

用样例试了一下,这里我们先只算以(i,j)为右下角时的情况

样例给的数据是

1
2
3
4
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

我们可以得到的dp结果是

1
2
3
4
0 1 0 1 0 0
0 0 2 0 2 0
1 1 0 0 0 3
0 1 1 0 1 0

不知道你们通过这样能不能推出来转移方程呢…

代码就贴在下面了,最后注意的细节是要搞两遍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
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define N 2502
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,a[N][N],ans=0,f[N][N];
int preleft[N][N],preup[N][N];
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!a[i][j])
{
preleft[i][j]=preleft[i][j-1]+1;
preup[i][j]=preup[i-1][j]+1;
}
else if(a[i][j])
{
f[i][j]=min(f[i-1][j-1]+1,min(preleft[i][j-1],preup[i-1][j])+1);
ans=max(ans,f[i][j]);
}
}
}
memset(preleft,0,sizeof(preleft));
memset(preup,0,sizeof(preup));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
if(!a[i][j])
{
preleft[i][j]=preleft[i][j+1]+1;
preup[i][j]=preup[i-1][j]+1;
}
else if(a[i][j])
{
f[i][j]=min(f[i-1][j+1]+1,min(preleft[i][j+1],preup[i-1][j])+1);
ans=max(ans,f[i][j]);
}
}
}
printf("%d",ans);
return 0;
}

luoguP1156垃圾陷阱

这道题因为dp二维的设计卡了一个多小时…(哎,我也就这种垃圾水平了…)

看完题目大致就知道本题的dp转移的时候有两种策略了,一种是不垫,一种是垫,这个很好想

问题在于dp设的是几维和每一维表示的是什么,说实话我补了这几天的dp之后觉得dp题一大难点就是这个

其实这道题一维和二维都可以,而且以高度或生命值作为第二维都可以(当然,是我看了题解之后发现的)

我这里就说一下我的二维思路吧看了题解之后的,用背包看待这个问题,距离为背包容量,生命之为价值,

1
2
3
```cpp
dp[i][j+q[i].h]=max(dp[i][j+q[i].h],dp[i-1][j]-(q[i].t-q[i-1].t));//垫
dp[i][j]=max(dp[i][j],dp[i-1][j]+q[i].f-(q[i].t-q[i-1].t));//不垫

遇到体力达不到的,直接continue

1
if(dp[i-1][j]<q[i].t-q[i-1].t)continue;

一开始不知道怎么判断什么时候出去,后来瞄了一眼题解真有道理,只要

1
j+q[i].h>=D

并且

1
dp[i-1][j]

有状态存着,就说明可以出去

如果不能出去呢?我以为只要取最后的

1
dp[G][i]+q[G]. t

的最大值,也就是

1
dp[G][0]+q[G].t

但是其实…问题是最后几个食物不一定能吃到!对!我那个wa的点就是这样,所以要取

1
dp[i][0]+a[i].t

中的最大值

代码

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
#include <bits/stdc++.h>
#define N 1000
#define inf 2147483647
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int t,f,h;
bool operator < (const node &a)const
{
return t<a.t;
}
}q[N];
int D,G,dp[N][N],ans=-inf;//dp[i][j]:i food j height max health
int main()
{
D=read(),G=read();
for(int i=1;i<=G;i++)
{
q[i].t=read(),q[i].f=read(),q[i].h=read();
}
sort(q+1,q+1+G);
for(int i=1;i<=G;i++)
{
for(int j=D;j>=0;j--)
{
dp[i][j]=-inf;
}
}
dp[0][0]=10;
q[0].t=0;
for(int i=1;i<=G;i++)
{
for(int j=D;j>=0;j--)
{
if(dp[i-1][j]<q[i].t-q[i-1].t)continue;
if(j+q[i].h>=D)
{
printf("%d",q[i].t);
return 0;
}
dp[i][j+q[i].h]=max(dp[i][j+q[i].h],dp[i-1][j]-(q[i].t-q[i-1].t));
dp[i][j]=max(dp[i][j],dp[i-1][j]+q[i].f-(q[i].t-q[i-1].t));
}
ans=max(ans,q[i].t+dp[i][0]);
}
printf("%d",ans);
return 0;
}

luoguP3959宝藏

这个题,去年写的时候几乎什么图的东西都没接触过…然后,直接爆零……

现在来看,说实话…也没什么思路…今天先是用最短路尝试了一下,发现可以卡过45分(废话那45分就是留给最短路的怎么卡都能过desu!
代码

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
void spfa(int x)
{
queue <int> d;
d.push(x);
inq[x]=1;
dist[x]=0;
pre[x]=0;
while(!d.empty())
{
int u=d.front();
d.pop();
inq[u]=0;
for(int i=head[u];i!=-1;i=q[i].next)
{
int v=q[i].to;
if(dist[v]>dist[u]+q[i].w)
{
dist[v]=dist[u]+q[i].w;
prepoint[v]=u;
pre[v]=pre[u]+1;
if(!inq[v])
{
inq[v]=1;
d.push(v);
}
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
n=read(),m=read();
memset(dis,0x7f,sizeof(dis));
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
add(x,y,z);
dis[x][y]=dis[y][x]=min(z,dis[x][y]);
}
for(int i=1;i<=n;i++)//start point
{
s=0;
memset(inq,0,sizeof(inq));
memset(pre,0,sizeof(pre));
memset(prepoint,0,sizeof(prepoint));
memset(dist,0x7f,sizeof(dist));
spfa(i);
for(int j=1;j<=n;j++)
{
if(j!=i)
{
s+=dis[prepoint[j]][j]*pre[j];
}
}
ans=min(ans,s);
}
printf("%d",ans);
return 0;
}

然后瞄了几眼题解,暴搜有70分?确实,因为n<=8,用dfs暴力把每种情况都搞出来,复杂度其实并不大
代码

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
#include <bits/stdc++.h>
#define N 100000
#define inf (1<<30)
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,dis[20][20],pre[20],ans=inf,s;
inline void dfs(int step)
{
if(step==n)
{
ans=min(ans,s);
return ;
}
if(s>=ans)return ;
for(int i=1;i<=n;i++)//下一步往哪
{
if(pre[i])continue;
for(int j=1;j<=n;j++)//由谁出发去找
{
if(dis[i][j]!=2139062143&&pre[j]&&i!=j)
{
s+=pre[j]*dis[i][j];
pre[i]=pre[j]+1;
dfs(step+1);
s-=pre[j]*dis[i][j];
pre[i]=0;
}
}
}
}
int main()
{
n=read(),m=read();
memset(dis,0x7f,sizeof(dis));//2139062143
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
dis[x][y]=dis[y][x]=min(z,dis[x][y]);
}
for(int i=1;i<=n;i++)
{
pre[i]=1;
s=0;
dfs(1);
pre[i]=0;
}
printf("%d",ans);
return 0;
}

这道去年的题让我清晰地认识到代码中细节的重要性和联赛中暴力的重要性…这十天也应该将暴力练好,争取打出高级暴力!rp++!

luoguP3399丝绸之路

这个题是个很好的线性dp题,而且特点也非常鲜明,初始化(我看了别人的思路)+转移方程(很简单)就没了,也是帮助我练了一下dp吧
我们设计状态,dp【i】【j】表示i城市j天的最小疲劳度,很容易就想到当i=j时,dp【i】【j】应该时每一天都不停

1
dp[i][i]=dp[i-1][i-1]+d[i]*c[i];

转移方程

1
dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j]);

最后取答案的时候

1
2
3
4
5
6
7
for(int i=1;i<=m;i++)
{
if(dp[n][i])
{
ans=min(ans,dp[n][i]);
}
}

luoguP2279消防局的设立

理论上这个题是一个有难度的dp题,然而…看了看算法标签…贪心!

在贪心的算法标签+自己的一个关于让一个点的祖父成为消防站的猜想+第一篇题解的思路,我写了一个循环里面套dfs的超级暴力的方法…然后居然a了

这里的贪心思路就是,既然要使消防站的数量最少,那么毫无疑问每一个消防站覆盖的扑灭火灾的范围应该尽可能的大。对于一个点,他要被覆盖,消防站与他的距离一定小于等于2,他的父亲,兄弟和祖父都满足这个条件,虽说这三者都可以互相覆盖,但祖父的覆盖范围肯定是最大的,所以贪心地选他的祖父为消防站

我们先dfs找到每个点的深度,接着按深度排序,从深至浅,这样可以保证每个点的子孙后代都在之前就被覆盖,遇到一个没有被覆盖(标记)的点,就以他的祖父dfs标记周围距他2距离的点,ans++,没了

贪心代码

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
#include <bits/stdc++.h>
#define N 2066
#define int long long
#define inf 2147483647
using namespace std;
typedef pair<int,int > p2;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,num=0,head[N],deep[N],fa[N],flag[N],ans=0;
struct node
{
int to,next;
}q[N];
struct point
{
int id;
int dep;
bool operator < (const point &b)const
{
return dep>b.dep;
}
}a[N];
void add(int x,int y)
{
q[num]=(node){y,head[x]};
head[x]=num++;
q[num]=(node){x,head[y]};
head[y]=num++;
}
void dfs(int x,int father,int dep)
{
fa[x]=father;
deep[x]=dep;
for(int i=head[x];i!=-1;i=q[i].next)
{
int v=q[i].to;
if(v!=fa[x])
{
dfs(v,x,dep+1);
}
}
}
void work(int x,int step)
{
if(step==2)return ;
for(int i=head[x];i!=-1;i=q[i].next)
{
int v=q[i].to;
flag[v]=1;
work(v,step+1);
}
}
signed main()
{
memset(head,-1,sizeof(head));
n=read();
for(int i=2;i<=n;i++)
{
int x=read();
add(i,x);
}
dfs(1,0,1);
for(int i=1;i<=n;i++)
{
a[i].id=i;
a[i].dep=deep[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(flag[a[i].id])continue;
flag[fa[fa[a[i].id]]]=1;
work(fa[fa[a[i].id]],0);
ans++;
}
printf("%lld",ans);
return 0;
}

luoguP3942将军令

与上一题类似,不过当你把2改为k之后交上去会发现…T了!
没错,这个题可不像上一题那么仁慈,数据范围那么小
如何应对?

其实,我们发现,以一个点的k父(毕竟这里不一定是祖父了吧…)向周围打标,其实就是从当前这个点往不是自己后代的方向找离他距离小于等于2*k的点就行了,这些点都是k父消防站所覆盖的,这个结论可以画一些树得知

所以我们不用去找一个点的k父,直接从当前点找,这样会省很多时间(好吧也就几百万的样子)
这里就贴一下work函数

1
2
3
4
5
6
7
8
9
10
11
void work(int x,int step,int son)
{
if(step==4)return ;
for(int i=head[x];i!=-1;i=q[i].next)
{
int v=q[i].to;
if(v==son)continue;
flag[v]=1;
work(v,step+1,x);
}
}

主函数相应部分

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
{
if(flag[a[i].id])continue;
flag[a[i].id]=1;
work(a[i].id,0,0);
ans++;
}