POJ - 1463 Strategic game (树状动态规划)
2024-08-28 14:42:24
这题做的心塞。。。
整个思路非常清晰,d[i][0]表示第i个结点不设置监察的情况下至少需要的数量;d[i][1]表示第i个结点设置检查的情况下的最小需要的数量。
状态转移方程见代码。
但是万万没想到的是,在实现过程中修改了4遍代码,wa了若干次才AC。。。。
下面来总结一下各种wa代码:
版本1:开二维数组存储树(本质上是邻接矩阵存储,把树存储成图),报错TLE。这时候第一感觉是每次更新d[i]的时候都需要遍历一遍邻接表中的所有结点不管是否是子节点都需要遍历。也就是完整的n*n复杂度。因此有了第一次修改,考虑存储的时候用vector只存储子节点从而减少遍历时的数量。(见版本2)
上代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<algorithm>
using namespace std;
//TLE 应该是在更新d[i][]的时候每次都需要遍历n个数,复杂度为o(n^2)
const int maxn=;
int d[maxn][];
int gra[maxn][maxn];
int flag[maxn];
int n;
void dp(int cur){
flag[cur]=;
if(d[cur][]>=||d[cur][]>=){
return;
}
int leaf=;
for(int i=;i<n;i++){
if(gra[cur][i]&&flag[i]!=){
leaf=;
dp(i);
if(d[cur][]==-)d[cur][]=;
if(d[cur][]==-)d[cur][]=;
d[cur][]+=d[i][];
d[cur][]+=min(d[i][],d[i][]);
}
}
d[cur][]++;
if(leaf==){
d[cur][]=;d[cur][]=;
}
}
int main(void){
while(scanf("%d",&n)){
memset(flag,,sizeof(flag));
memset(gra,,sizeof(gra));
memset(d,-,sizeof(d));
int x,cnt;
int num=n;
while(num--){
scanf("%d:(%d)",&x,&cnt);
while(cnt--){
int tem;
scanf("%d",&tem);
gra[x][tem]=;
gra[tem][x]=;
}
}
dp(x);
int ans=min(d[x][],d[x][]);
cout<<ans<<endl;
}
return ;
}
版本2代码:拟通过vector减少遍历的结点个数(只遍历子节点)。这次修改后果然没有报TLE,但是报了另外一个错:MLE。。。
所以说使用stl还是要慎重。。这时再看了一遍输入样例,发现其实这个输入是按标准的有向树输入的;换句话说根本不需要构造图来解,只需要每个结点记录其父亲即可。
这样一算,存储的数据量瞬间减半。因此有了版本3代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
using namespace std;
//memory limit
const int maxn=;
int d[maxn][];
//int gra[maxn][maxn];
vector<int>gra[maxn];
bool flag[maxn];
int n;
void dp(int cur){
flag[cur]=;
if(d[cur][]>=||d[cur][]>=){
return;
}
else{
int leaf=;
for(int i=;i<gra[cur].size();i++){
int next=gra[cur][i];
if(flag[next]==){
leaf=;
dp(next);
if(d[cur][]==-)d[cur][]=;
if(d[cur][]==-)d[cur][]=;
d[cur][]+=d[next][];
d[cur][]+=min(d[next][],d[next][]);
}
}
d[cur][]++;
if(leaf==){
d[cur][]=;d[cur][]=;
}
}
}
int main(void){
while(scanf("%d",&n)!=EOF){
memset(flag,,sizeof(flag));
memset(gra,,sizeof(gra));
memset(d,-,sizeof(d));
int x,cnt;
int num=n;
while(num--){
scanf("%d:(%d)",&x,&cnt);
while(cnt--){
int tem;
scanf("%d",&tem);
gra[x].push_back(tem);
gra[tem].push_back(x);
}
}
dp(x);
int ans=min(d[x][],d[x][]);
cout<<ans<<endl;
}
return ;
}
版本3代码:本来以为这个可以直接AC的,结果又一次TLE。。。而且这次的错误找了好久没想到。
最后发现出现在了scanf上。。。
版本3中的代码while(scanf("%d",&n)) 改成while(scanf("%d",&n)!=EOF)或者while(~scanf("%d",&n))就AC了(真的是,秀了一波骚操作。侧面反映基础不太扎实。。。。)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int d[maxn][];
int pre[maxn];
int childcnt[maxn];
int n;
void dp(int cur){
if(d[cur][]>=||d[cur][]>=){
return;
}
if(childcnt[cur]==){
d[cur][]=;d[cur][]=;
return ;
}
for(int i=;i<n;i++){
if(pre[i]==cur){
dp(i);
if(d[cur][]==-)d[cur][]=;
if(d[cur][]==-)d[cur][]=;
d[cur][]+=d[i][];
d[cur][]+=min(d[i][],d[i][]);
}
}
d[cur][]++;
}
int main(void){
while(scanf("%d",&n)){
memset(pre,-,sizeof(pre));
memset(d,-,sizeof(d));
int x,cnt,root=-;
int num=n;
while(num--){
scanf("%d:(%d)",&x,&cnt);
childcnt[x]=cnt;
if(root==-)root=x;
while(cnt--){
int tem;
scanf("%d",&tem);
pre[tem]=x;
if(tem==root){
root=x;
}
}
}
dp(root);
int ans=min(d[root][],d[root][]);
printf("%d\n",ans);
}
return ;
}
AC代码如下:哎,任重而道远,,,太菜了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int d[maxn][];
int pre[maxn];
int childcnt[maxn];
int n;
void dp(int cur){
if(d[cur][]>=||d[cur][]>=){
return;
}
if(childcnt[cur]==){
d[cur][]=;d[cur][]=;
return ;
}
for(int i=;i<n;i++){
if(pre[i]==cur){
dp(i);
if(d[cur][]==-)d[cur][]=;
if(d[cur][]==-)d[cur][]=;
d[cur][]+=d[i][];
d[cur][]+=min(d[i][],d[i][]);
}
}
d[cur][]++;
}
int main(void){
while(scanf("%d",&n)!=EOF){//万万没想到是这里出错
memset(pre,-,sizeof(pre));
memset(d,-,sizeof(d));
int x,cnt,root=-;
int num=n;
while(num--){
scanf("%d:(%d)",&x,&cnt);
childcnt[x]=cnt;
if(root==-)root=x;
while(cnt--){
int tem;
scanf("%d",&tem);
pre[tem]=x;
if(tem==root){
root=x;
}
}
}
dp(root);
int ans=min(d[root][],d[root][]);
printf("%d\n",ans);
}
return ;
}
最新文章
- 自定义鼠标光标cursor
- druid连接池获取不到连接的一种情况
- 阿里提前批校招内推offer经历
- JVM复习笔记
- hdu 5172 GTY&#39;s gay friends
- Alternating Current
- Android 内部存储相关的函数(getCacheDir,getDir, getFileStreamPath,getFilesDir,openFileInput, ...)
- 基于RSA securID的Radius二次验证java实现(PAP验证方式)
- uva 1560 - Extended Lights Out(枚举 | 高斯消元)
- Plan : 破晓
- 基于Levenberg-Marquardt训练算法的BP网络Python实现
- 安装Genymotion与集成eclipse,最后有集成android studio
- python 判断网络通断同时检测网络的状态
- hdu 2364 Escape【模拟优先队列】【bfs】
- Nginx配置详细
- Node JS 8 如何在浏览器上在线调试
- [转] 在 Windows 中让任务栏时间显示&ldquo;秒&rdquo;
- OG数据预处理
- ecshop,大商创后台支付系统修改模板
- Mac iTerm2使用总结