选取的做题记录


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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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;
}
struct node
{
int fr,to,w,next;
}q[N];
int n,m,head[N],num=0,ans=inf,s,pre[20],prepoint[20],dis[20][20],dist[20];
bool inq[20];
void add(int x,int y,int z)
{
q[num]=(node){x,y,z,head[x]};
head[x]=num++;
q[num]=(node){y,x,z,head[y]};
head[y]=num++;
}
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;
}

然后,据题解的说法,疯狂剪枝加各种玄学优化,就可以a,然后我就快乐地抄了一波题解实属无耻之举,不过说真的我也不会状压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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define N 100000
using namespace std;
const int inf=2139062143;
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,ans=inf,s,tmp,sum,p;//tmp剪枝,cnt访问过的点,p来sort
int inq[20],l[20],d[20];//inq已经访问过的点,l点距离初始点的距离,d每个点连出去几个点
int cost[20][20],canto[20][20];//canto每个点能到的点
bool cmp(int a,int b)
{
return cost[p][a]<cost[p][b];
}
void dfs(int x,int node)
{
for(int i=x;i<=sum;i++)
{
if(s+tmp*l[inq[i]]>=ans)return ;
for(int j=node;j<=d[inq[i]];j++)
{
if(l[canto[inq[i]][j]])continue;
sum++;
inq[sum]=canto[inq[i]][j];
tmp-=cost[inq[sum]][canto[inq[sum]][1]];
s+=cost[inq[i]][inq[sum]]*l[inq[i]];
l[inq[sum]]=l[inq[i]]+1;
dfs(i,j+1);
s-=cost[inq[i]][inq[sum]]*l[inq[i]];
l[inq[sum]]=0;
tmp+=cost[inq[sum]][canto[inq[sum]][1]];
sum--;
}
node=1;
}
if(sum==n)
{
if(s<ans)ans=s;
return ;
}
}
int main()
{
n=read(),m=read();
memset(cost,0x7f,sizeof(cost));
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
if(cost[x][y]<z)continue;
if(cost[x][y]==inf)
{
canto[x][++d[x]]=y;
canto[y][++d[y]]=x;
}
cost[x][y]=cost[y][x]=z;
}
for(int i=1;i<=n;i++)
{
p=i;
sort(canto[i]+1,canto[i]+1+d[i],cmp);
tmp+=cost[i][canto[i][1]];
}
for(int i=1;i<=n;i++)
{
s=0;
sum=1;
inq[1]=i;
tmp-=cost[i][canto[i][1]];
l[i]=1;
dfs(1,1);
l[i]=0;
tmp+=cost[i][canto[i][1]];
}
printf("%d",ans);
return 0;
}

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