2/20 树上dp+正方形个数问题(dp)+dfs+连通块+背包
20 DP 个数 DFS 背包 连通 正方形 问题
2023-09-11 14:15:53 时间
P1352 没有上司的舞会
https://www.luogu.com.cn/problem/P1352
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct node
{
int to,nxt;
}e[maxn];
int n,r[maxn],f[maxn][4],head[maxn],cnt,in[maxn];
void add(int from,int to)
{
e[++cnt].to=to;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
dfs(v);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
f[u][1]+=r[u];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
for(int i=1;i<=n-1;i++)
{
int u,v;scanf("%d%d",&u,&v);
in[u]++; //入度
add(v,u);
}
int g;
for(int i=1;i<=n;i++)
{
if(!in[i])
{
g=i;
break;
}
}
dfs(g); //从根开始,因此跟记录最大值
cout<<max(f[g][0],f[g][1])<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P2014
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
struct node
{
int to,nxt;
}e[maxn];
int n,m,r[maxn],f[maxn][maxn],head[maxn],cnt,in[maxn];
void add(int from,int to)
{
e[++cnt].to=to;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dfs(int u,int num)
{
if(num<=0) return;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
for(int j=0;j<num;j++)
f[v][j]=f[u][j]+r[v]; //加上当前结点的值
dfs(v,num-1);
for(int j=1;j<=num;j++)
f[u][j]=max(f[u][j],f[v][j-1]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int v;scanf("%d%d",&v,&r[i]);
add(v,i);
}
dfs(0,m);
cout<<f[0][m]<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P2733
#include <bits/stdc++.h>
using namespace std;
const int maxn=300;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int n,f[maxn][maxn],num[100005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='1')
f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
num[f[i][j]]++;
}
}
for(int i=n;i>=1;i--)
num[i-1]+=num[i];
for(int i=2;i<=n;i++)
{
if(num[i])
cout<<i<<" "<<num[i]<<endl;
}
return 0;
}
https://www.luogu.com.cn/problem/P2040
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+5;
int mp[5][5],ans,tmp=10;
bool vis[maxn][maxn];
void change(int x,int y)
{
mp[x][y]^=1;
mp[x+1][y]^=1;
mp[x-1][y]^=1;
mp[x][y+1]^=1;
mp[x][y-1]^=1;
}
void dfs(int step)
{
if(step>tmp)
return;
int s=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
s+=mp[i][j];
if(s==9)
{
ans=step-1;
if(tmp>ans)
tmp=ans;
}
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
change(i,j);
dfs(step+1);
change(i,j); //回溯
}
}
return;
}
int main()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
cin>>mp[i][j];
dfs(1);
cout<<tmp<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P2052
上连通块-下连通块 的绝对值乘以距离的和
(采用深搜)
num 记录以i为根的子树的大小
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e6+5;
int n,m,num[maxn],f[maxn],head[maxn],cnt,ans;
struct node
{
int to,dis,nxt;
}e[maxn];
void add(int from,int to,int dis)
{
e[++cnt].to=to;
e[cnt].dis=dis;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dfs(int u,int pre)
{
num[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==pre)
continue;
dfs(v,u);
num[u]+=num[v];
ans+=e[i].dis*abs(2*num[v]-n);
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n-1;i++)
{
int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P2214
记录每个牧场真是音量
其中f[i]
表示音量为i的最小奶牛数,然后用音量最大的牧场进行完全背包。
最后加上每个牧场音量的最小奶牛数目
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int n,b,v[maxn],w[maxn],g[maxn],f[maxn],mx,ans;
int main()
{
scanf("%d%d",&n,&b);
for(int i=1;i<=b;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
g[i]=w[i]-max(w[i-1]-1,0);
mx=max(mx,g[i]);
}
memset(f,inf,sizeof(f));
f[0]=0;
for(int i=1;i<=b;i++) //农场数
{
for(int j=v[i];j<=mx;j++)
f[j]=min(f[j],f[j-v[i]]+1);
}
for(int i=1;i<=n;i++)
{
ans+=f[g[i]];
}
cout<<ans<<endl;
return 0;
}
相关文章
- C语言程序设计100例之(20):过河卒
- 1084. Broken Keyboard (20)
- 《惢客创业日记》2019.06.20(周四)启用团队协作管理系统
- English trip V2 - 20 New Friends 新朋友 Teacher: Taylor
- 3/20 思维+双指针
- 戴文的Linux内核专题:20 配置内核 (16)
- 2018年1月20日上海MVP线下技术分享会纪实
- ChatGPT 的 20 种有趣用途,您可能不知道
- 剑指 Offer 20. 表示数值的字符串
- delphi如何按照控件的左右顺序来遍历窗体中的每个控件 [问题点数:20 http://bbs.csdn.net/topics/380216822
- 大数据被盗 案值20亿?!
- 20 Best Drag and Drop jQuery Plugins--reference