锐客网

  1. 首页 > it技术 > >

将军令（贪心算法）

当然如果你想像考场上傻掉的我一样打树上dp，那祝你码得愉快了。
将军令（贪心算法）
文章图片
将军令（贪心算法）
文章图片

1 #include 2 using namespace std; 3 #define set(p) memset(dp[p],0x3f,sizeof(dp[p])) 4 int dp[100005][5][5],n,fir[100005],l[200005],to[200005],cnt,k,p; 5 void connect(int a,int b){ 6l[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; 7l[++cnt]=fir[b]; fir[b]=cnt; to[cnt]=a; 8 } 9 void dfs(int p,int f){ 10for(int ii=fir[p]; ii; ii=l[ii])if(to[ii]!=f)dfs(to[ii],p); 11int t=100002,tt=100003; set(t); memset(dp[t],0,sizeof(dp[t])); dp[t][0][0]=1; 12for(int ii=fir[p]; ii; ii=l[ii])if(to[ii]!=f){ 13t^=1; tt^=1; set(t); 14for(int i=0; i<=k+1; ++i)for(int j=0; j<=k; ++j) 15dp[t][0][0]=min(dp[t][0][0],dp[tt][0][0]+dp[to[ii]][i][j]); 16for(int i=0; i<=k+1; ++i)for(int j=0; j<=k; ++j) 17for(int x=0; x<=k+1; ++x)for(int y=0; y<=k; ++y) if(x+j<=k&&i+y<=k) 18dp[t][min(i,x+1)][max(j,y+1)]=min(dp[t][min(i,x+1)][max(j,y+1)],dp[tt][i][j]+dp[to[ii]][x][y]); 19for(int i=0; i<=k+1; ++i)for(int j=0; j
先交的40分。只能处理k=1的树上dp 将军令（贪心算法）
文章图片
将军令（贪心算法）
文章图片
1 #include 2 using namespace std; 3 #define set(p) memset(dp[p],0x3f,sizeof(dp[p])) 4 int dp[100005][11][11],n,fir[100005],l[200005],to[200005],cnt,k,p; 5 void connect(int a,int b){ 6l[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; 7l[++cnt]=fir[b]; fir[b]=cnt; to[cnt]=a; 8 } 9 void dfs(int p,int f){ 10for(int ii=fir[p]; ii; ii=l[ii])if(to[ii]!=f)dfs(to[ii],p); 11int t=100002,tt=100003; set(t); dp[t][k][0]=0; dp[t][0][0]=1; 12for(int ii=fir[p]; ii; ii=l[ii])if(to[ii]!=f){ 13t^=1; tt^=1; set(t); 14for(int i=0; i<=k+1; ++i)for(int j=0; j<=k; ++j) 15dp[t][0][0]=min(dp[t][0][0],dp[tt][0][0]+dp[to[ii]][i][j]); 16for(int i=0; i<=k+1; ++i)for(int j=0; j<=k; ++j) 17for(int x=0; x<=k+1; ++x)for(int y=0; y<=k; ++y) if(x+j<=k&&i+y<=k) 18dp[t][min(i,x+1)][max(j,y+1)]=min(dp[t][min(i,x+1)][max(j,y+1)],dp[tt][i][j]+dp[to[ii]][x][y]); 19for(int i=0; i<=k+1; ++i)for(int j=0; j
盖掉它的0分代码（没删调试语句）实际上是20分） 当然贪心这种东西除非会证明不然是真的不敢打。上次的T1就没发现那是一个贪心然而证明了正确性。。。
当然这次根本没有往那个方向上去想。
将军令（贪心算法）
文章图片

【将军令（贪心算法）】这个写的太好了。我无法反驳（因为它就是对的）
所以，就没了！
我们只需要维护一个数组f，表示从这个点开始多大的范围内能都被控制。
那么我们在一个新的位置上设置守卫时这个位置的f就是k
尝试更新与它相邻的点，它们的f在已有的f和k-1中取max就好。
然后同理继续向外扩散就好了。初值要赋成-1，那么f！=-1就表示这个点已经被看守了。
将军令（贪心算法）
文章图片
将军令（贪心算法）
文章图片
1 #include 2 using namespace std; 3 priority_queueint,int> >q; 4 int res[100005],cnt,n,k,t,fir[100005],l[200005],to[200005],f[100005],ans; 5 void link(int a,int b){l[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; } 6 void pre_dfs(int p,int fa,int dep){ 7q.push(make_pair(dep,p)); res[p]=-1; f[p]=fa; 8for(int i=fir[p]; i; i=l[i])if(to[i]!=fa)pre_dfs(to[i],p,dep+1); 9 } 10 void dfs(int p){ 11for(int i=fir[p]; i; i=l[i])if(res[to[i]]=0)continue; 20for(int i=1; i<=k; ++i)if(f[p])p=f[p]; 21res[p]=k; dfs(p); ans++; 22} 23printf("%d\n",ans); 24 }

773B的小东西
转载于:https://www.cnblogs.com/hzoi-DeepinC/p/11335266.html

    推荐阅读


    上一篇：两个线程交替打印0～100的奇偶数

    下一篇：入侵检测系统IDS