117 条题解
-
4larryzhong LV 9 @ 2017-10-05 21:50:31
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1550; int n, cost[maxn], dp[maxn][3]; bool root[maxn]; vector<int> G[maxn]; void dfs(int u) { int _min = 0x3f3f3f3f; for (int v : G[u]) { dfs(v); dp[u][0] += min(min(dp[v][0], dp[v][1]), dp[v][2]); dp[u][1] += min(dp[v][0], dp[v][1]); dp[u][2] += min(dp[v][0], dp[v][1]); _min = min(_min, dp[v][0] - min(dp[v][0], dp[v][1])); } dp[u][0] += cost[u]; dp[u][1] += _min; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) { int u, c, m, v; cin >> u >> c >> m; cost[u] = c; while (m--) { cin >> v; root[v] = true; G[u].push_back(v); } } for (int i = 1; i <= n; i++) { if (!root[i]) { dfs(i); cout << min(dp[i][0], dp[i][1]) << endl; break; } } return 0; }
-
32017-10-05 21:52:27@
f[0][x] 表示以x为根的子树已经被控制好,且x也被控制好,x放守卫。
f[1][x] 表示以x为根的子树已经被控制好,且x也被控制好,x不放守卫。
f[2][x] 表示以x为根的子树已经被控制好,但x没有被控制,且x不放守卫。
f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点)
f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min;
f[2][x]=∑f[1][y]; -
22016-08-20 23:32:31@
链式前向星+动态规划。有点坑。看代码注释去。
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;
#define INF 100000000
//不用数了,上面是1亿,9位,8个0.
int to[3001],pre[6001],last[6001];//链式前向星各数组
int dp[3001][3];//f(i,j)对于编号i的点,j=0表示由子节点守卫时最小花费,j=1表示由自己守卫最小花费,j=2表示由父节点守卫最小花费
int cost[3001];//顾名思义
int id=0;//给边编号用
void add(int a,int b)//连一条a->b的单向线
{
pre[++id]=last[a];//标记同样由a出发的上一条边是哪条
to[id]=b;//标记这条边连向b
last[a]=id;//标记最后一条边为这条边
}
void dfs(int now,int father)
{
dp[now][1]=cost[now];
dp[now][2]=0;
//上为初始化
int flag=INF;//flag是精华!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
for(int i=last[now]; i; i=pre[i]) {//枚举以now这个点为起点的每一条边
if(to[i]!=father) {//如果某一个点和他连接又不是父节点,那就是子节点。
dfs(to[i],now);//要由叶子节点推到根节点。dfs下一层dp[now][0]+=min(dp[to[i]][1],dp[to[i]][0]);
//前者优时,状态确定。父节点(to[i])更划算,守卫!
//当后者优时,状态不确定:now让子节点守护,这个子节点又让子节点守护,不清真!
dp[now][1]+=min(dp[to[i]][1],min(dp[to[i]][2],dp[to[i]][0]));//状态确定。
dp[now][2]+=min(dp[to[i]][0],dp[to[i]][1]);//状态确定。
//以下处理dp[now][0]巨坑。
if(dp[to[i]][1]<=dp[to[i]][0]) //now节点的这个儿子自己有了守卫(同时守卫了now),不用强迫放置守卫于某个子节点(to[i])
flag=0;
if(flag&&dp[to[i]][1]-dp[to[i]][0]<flag) {
//万一父节点没放(to[i])可能要必须放(出现dp[now][0]求值时min函数中后者优的情况,
//必须有一个子节点(to[i])来保护父节点(now)),记录放父节点和原来所增加的额外费用。
//(当然如果某个子节点已经保护了,补差价0元:不用强迫放置守卫于子节点(to[i]))
//如果都没保护父节点(now),挑一个最划算的,补最小的差价,差价最小多少?没错,在flag里。
flag=dp[to[i]][1]-dp[to[i]][0];//得出:子节点(to[i])自己守卫 & 子节点(to[i])由其子节点(to[i]的子节点)守卫 的差价。 强行放守卫贵了flag这么多。
}
}
}
dp[now][0]+=flag;//补差价
}
int main()
{
int n;
scanf("%d",&n);//n个节点
for (int i=1;i<=n;i++) {
int a,b,k;
scanf("%d",&a);//节点编号
scanf("%d",&cost[a]);//节点放置守卫经费
scanf("%d",&k);//子节点数
while(k--) {
scanf("%d",&b);//子节点
add(a,b);//a->b
add(b,a);//b->a
//子节点父节点连边,注意双向
}
}
dfs(1,0);//作用:由下往上推,最后守卫网络将覆盖到编号为1的点(根节点) ,搞到这时的最小花费 。第二个参数为父节点,根节点(节点1)无父节点,传入0.
printf("%d",min(dp[1][0],dp[1][1]));//输出,没有dp[1][2],因为根节点没有父亲
return 0;
} -
12018-02-23 20:35:52@
根节点没有父亲,因此取最小值只能去儿子和自己的
树形DP+邻接表,没有用二叉链表结构,直接多叉树求解
#include<cstdio> #include<iostream> #include<cstring> #define MAXN 1501 #define INF 2100000000 using namespace std; int n, c[MAXN]; int from[MAXN], to[MAXN], first[MAXN], nxt[MAXN]; int indeg[MAXN] = {0}; int dp[MAXN][3] = {0}; // 0->son, 1->self, 2->pa void dfs(int i){ int e = first[i]; int sonmin, selfmin, pamin, diffmin; diffmin = INF; while(e){ dfs(to[e]); sonmin = selfmin = pamin = INF; selfmin = min(selfmin, dp[to[e]][0]); selfmin = min(selfmin, dp[to[e]][1]); selfmin = min(selfmin, dp[to[e]][2]); dp[i][1] += selfmin; sonmin = min(sonmin, dp[to[e]][0]); sonmin = min(sonmin, dp[to[e]][1]); diffmin = min(diffmin, dp[to[e]][1]-sonmin); dp[i][0] += sonmin; dp[i][2] += sonmin; e = nxt[e]; } dp[i][0] += diffmin; dp[i][1] += c[i]; // cout << endl << i << " : " << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl; return; } int main(){ int ti, tn, tto, mcnt = 0, t; cin >> n; for(int i=0; i<n; i++){ cin >> ti; cin >> c[ti]; cin >> tn; for(int j=0; j<tn; j++){ mcnt ++; cin >> tto; from[mcnt] = ti; to[mcnt] = tto; t = first[ti]; first[ti] = mcnt; nxt[mcnt] = t; indeg[tto]++; } } int gans = 0; for(int i=1; i<=n; i++){ if(!indeg[i]){ memset(dp, 0, sizeof(dp)); dfs(i); gans += min(dp[i][0], dp[i][1]); } } cout << gans << endl; return 0; }
评测情况
Accepted # 状态 耗时 内存占用 #1 Accepted 3ms 340.0 KiB #2 Accepted 3ms 372.0 KiB #3 Accepted 4ms 356.0 KiB #4 Accepted 4ms 504.0 KiB #5 Accepted 7ms 352.0 KiB #6 Accepted 6ms 376.0 KiB #7 Accepted 3ms 352.0 KiB
-
12016-11-04 15:52:36@
dp................
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
const int N=1505;
int n,a[N],nums[N],son[N][N],f[N][3];
bool v[N];void dp(int root)
{
int tmp;
if(nums[root]==0) return;
for(int i=1;i<=nums[root];i++) dp(son[root][i]);
tmp=1000000;
for(int i=1;i<=nums[root];i++)
{
f[root][0]=f[root][0]+min(min(f[son[root][i]][0],f[son[root][i]][1]),f[son[root][i]][2]);
f[root][1]=f[root][1]+min(f[son[root][i]][0],f[son[root][i]][1]);
if(f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1])<tmp)
tmp=f[son[root][i]][0]-min(f[son[root][i]][0],f[son[root][i]][1]);
f[root][2]=f[root][2]+f[son[root][i]][1];
}
f[root][0]=f[root][0]+a[root];
f[root][1]=f[root][1]+tmp;
}int main()
{
//freopen("guard.in","r",stdin);
//freopen("guard.out","w",stdout);
int x,d,k,root;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&d,&k);
a[x]=d;
nums[x]=k;
for(int j=1;j<=k;j++)
{
scanf("%d",&son[x][j]);
v[son[x][j]]=1;
}
}
for(int i=1;i<=n;i++)
if(!v[i])
{
root=i;
break;
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
if(nums[i]==0)
{
f[i][0]=a[i];
f[i][1]=1000000;
f[i][2]=0;
}
dp(root);
cout<<min(f[root][0],f[root][1])<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
} -
12016-09-29 06:58:34@
#include <cstdio> #include <cstdlib> #define maxn 1510 typedef struct node { int v; struct node *next; }poi; int n,father[maxn],a[maxn],root,f[3][maxn]; poi *l[maxn],*r[maxn]; poi *newnode() { poi *u=(poi*) malloc(sizeof(poi)); u->next=NULL; return u; } void input_data() { scanf("%d",&n); for (int i=1;i<=n;i++) l[i]=r[i]=newnode(),father[i]=i; for (int i=1;i<=n;i++) { int x,y,w,num; scanf("%d%d%d",&x,&w,&num); a[x]=w; for (int j=1;j<=num;j++) { scanf("%d",&y); r[x]=r[x]->next=newnode(); r[x]->v=y; father[y]=x; } } } int search_father(int x) { if (father[x] !=x) return (search_father(father[x])); else return x; } int min(int a,int b) { return a>b?b:a; } /* f[0][x] 表示以x为根的子树已经被控制好,且x也被控制好,x放守卫。 f[1][x] 表示以x为根的子树已经被控制好,且x也被控制好,x不放守卫。 f[2][x] 表示以x为根的子树已经被控制好,但x没有被控制,且x不放守卫。 f[0][x]=∑min{f[0][y],f[1][y],f[2][y]}+a[x]; (y是x的直系儿子节点) f[1][x]=∑min{f[0][y],f[1][y]}+(f[0][u]-f[1][u]);右半部分括号内的东西在y全都不放守卫时起作用。且(f[0][u]-f[1][u])min; f[2][x]=∑f[1][y]; */ void cm(int x) { poi *p=l[x]->next; bool bo=false; int special=10000; while (p!=NULL) { int y=p->v; if (y!=x) { cm(y); f[0][x]+=min(f[0][y],min(f[1][y],f[2][y])); if (f[0][y]<=f[1][y]) bo=true; if (special>f[0][y]-f[1][y]) special=f[0][y]-f[1][y]; f[1][x]+=min(f[0][y],f[1][y]); f[2][x]+=f[1][y]; } p=p->next; } if (!bo) f[1][x]+=special; f[0][x]+=a[x]; } int main() { input_data(); root=search_father(n); cm(root); printf("%d\n",min(f[1][root],f[0][root])); return 0; }
-
12016-06-29 18:04:18@
为了练习左子右兄法叫了好多次才发现错在哪里。。。
果然还是太弱了。。。
下面是核心:
void dp(int x)
{
if(x==0)return ;
int l=ch[x][0],r=ch[x][1];
dp(l);dp(r);
f[x][0][0]=f[l][1][0]+min(f[r][0][0],f[r][1][0]);
f[x][1][0]=min(f[l][1][0]+f[r][1][0] , min(f[l][1][1],f[l][0][1])+min(f[r][0][0],f[r][1][0])+v[x]);
f[x][0][1]=min(f[l][1][0],f[l][0][0])+min(f[r][0][1],f[r][1][1]);
f[x][1][1]=min(min(f[l][1][0],f[l][0][0])+f[r][1][1] , min(f[l][1][1],f[l][0][1])+min(f[r][0][1],f[r][1][1])+v[x]);
} -
12016-03-13 15:54:41@
不知道为什么一直过不了,希望能够帮忙看一下。
写的不算很丑,希望能认真的看一下。
thanks~
pascal
var
f:array[0..1500,0..2] of longint;
a:array[0..1500,0..1500] of longint;
w:array[0..1500] of longint;
n,i,j,k,m,x,root:longint;
function min(a,b:longint):longint;
begin
if a=0 then min:=b
else if b=0 then min:=a
else if a<b then min:=a
else min:=b;
end;
procedure dp(u:longint);
var
mm,i,v:longint;
begin
f[u,0]:=w[u]; mm:=maxlongint;
if a[u,0]=0 then exit;
for i:=1 to a[u,0] do
begin
v:=a[u,i];
dp(v);
f[u,0]:=f[u,0]+min(f[v,0],min(f[v,1],f[v,2]));
f[u,1]:=f[u,1]+min(f[v,0],f[v,1]);
f[u,2]:=f[u,2]+f[v,1];
mm:=min(mm,f[v,0]-f[v,1]);
end;
if mm>0 then f[u,1]:=f[u,1]+mm;
end;
begin
readln(n); root:=0;
for i:=1 to n do
begin
root:=root+i;
read(k,w[k],m);
for j:=1 to m do
begin
read(x);
inc(a[k,0]);
a[k,a[k,0]]:=x;
root:=root-x;
end;
readln;
end;
dp(root);
writeln(min(f[root,0],f[root,1]));
end.
-
02019-11-26 17:02:00@
看到各位dalao都用了dfs,嵌套循环的我瑟瑟发抖
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
struct line
{
int to,ne;
}st[1500];
long long a[1501],dp[1501][3];
int n,p,no,h[1501],s[1501],f[1501],vis[1501],ss[1501];
void add(int x,int y)
{
st[++p].to=y;
st[p].ne=h[x];
h[x]=p;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&no);
scanf("%lld%d",&a[no],&s[no]);
ss[no]=s[no];
for(int j=1;j<=s[no];j++)
{
int x;
scanf("%d",&x);
add(no,x);
vis[x]=1;
f[x]=no;
}
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
f[i]=0;
memset(vis,0,sizeof(vis));
break;
}
}
for(int j=1;j<=n;j++)
{
if(!ss[j])
{
dp[j][1]=a[j];
dp[j][0]=1e15+10;
dp[j][2]=0;
ss[f[j]]--;
vis[f[j]]=1;
ss[j]--;
}
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
for(int j=1;j<=n;j++)
{
if(f[j]==0&&ss[j]==-1)
{
printf("%lld",min(dp[j][0],dp[j][1]));
return 0;
}
if(ss[j]==0&&vis[j]==0)
{
int yes=1;
if(h[j]!=0)
yes=0;
for(int ii=h[j];ii;ii=st[ii].ne)
{
if(dp[st[ii].to][1]<=dp[st[ii].to][0])
yes=1;
dp[j][2]+=min(dp[st[ii].to][0],dp[st[ii].to][1]);
dp[j][1]+=min(dp[st[ii].to][0],min(dp[st[ii].to][1],dp[st[ii].to][2]));
}
dp[j][1]+=a[j];
dp[j][0]=dp[j][2];
if(!yes)
{
long long mi=1e15+10;
for(int ii=h[j];ii;ii=st[ii].ne)
{
mi=min(mi,dp[st[ii].to][1]-dp[st[ii].to][0]);
}
dp[j][0]+=mi;
}
ss[f[j]]--;
vis[f[j]]=1;
ss[j]--;}
}
}
return 0;
}
``` -
02017-09-22 20:27:28@
#include <stdio.h> using namespace std; int n; struct node { int fa; long long value; int childs; int child[1501]; }; node tree[1501]; long long f[1501][4]; int visited[1501]; int t[1501]; int root; int abs(int a) { if (a<0) return -a; else return a; } int min(int a,int b) { if (a<b) return a; else return b; } void dp(int now) { if (visited[now]==1||tree[now].childs==0) return; visited[now]=1; for (int i=1;i<=tree[now].childs;i++) dp(tree[now].child[i]); int temp=0; f[now][1]=tree[now].value; int minn=1000000; for (int i=1;i<=tree[now].childs;i++) { f[now][3]=f[now][3]+f[tree[now].child[i]][2]; f[now][1]=f[now][1]+min(min(f[tree[now].child[i]][1],f[tree[now].child[i]][2]),f[tree[now].child[i]][3]); if (f[tree[now].child[i]][1]<=f[tree[now].child[i]][2]) { temp=1; f[now][2]=f[now][2]+f[tree[now].child[i]][1]; } else f[now][2]=f[now][2]+f[tree[now].child[i]][2]; minn=min(minn,abs(f[tree[now].child[i]][1]-f[tree[now].child[i]][2])); } if (temp==0) f[now][2]=f[now][2]+minn; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { int t1,t2,t3; scanf("%d%d%d",&t1,&t2,&t3); tree[t1].value=t2; tree[t1].childs=t3; for (int j=1;j<=t3;j++) { int temp; scanf("%d",&temp); tree[temp].fa=i; tree[t1].child[j]=temp; t[temp]=1; } } for (int i=1;i<=n;i++) if (t[i]==0) root=i; for (int i=1;i<=n;i++) if (tree[i].childs==0) { f[i][1]=tree[i].value; f[i][2]=10000000; f[i][3]=0; } dp(root); printf("%d\n",min(f[root][1],f[root][2])); return 0; }
-
02017-09-15 08:23:02@
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1500+10; typedef long long ll; int last[N],n,len; ll dp1[N],dp2[N],dp3[N],w[N]; struct Edge{int to,next;Edge(int to=0,int next=0):to(to),next(next){}}e[N<<1]; void add_edge(int u,int v){e[++len]=Edge(v,last[u]);last[u]=len;} void dp(int x,int fa) { ll mn=(1<<30); dp1[x]=dp2[x]=dp3[x]=0; for(int i=last[x];i;i=e[i].next) { int id=e[i].to; if(id==fa)continue; dp(id,x); dp1[x]+=min(dp1[id],min(dp2[id],dp3[id])); dp2[x]+=min(dp1[id],dp2[id]); ll t=dp1[id]-min(dp1[id],dp2[id]); mn=min(mn,t); dp3[x]+=min(dp1[id],dp2[id]); } dp2[x]+=mn;dp1[x]+=w[x]; } int main() { memset(dp1,127,sizeof(dp1)); memset(dp2,127,sizeof(dp2)); memset(dp3,127,sizeof(dp3)); scanf("%d",&n); for(int i=1;i<=n;i++) { int cur,K,num,son; scanf("%d%d%d",&cur,&K,&num); w[cur]=K; while(num--){scanf("%d",&son);add_edge(cur,son);add_edge(son,cur);} } dp(1,0); printf("%lld\n",min(dp1[1],dp2[1])); return 0; }
-
02017-07-05 10:16:05@
/* z.s */
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1505;
int n;
vector<int> q[maxn];
int w[maxn];
int f1[maxn],f2[maxn],f3[maxn];
int f[maxn];
int ans;
void dfs(int rt)
{
int cnt=0x7f7f7f7f;
for(int i=0;i<q[rt].size();i++)
{
int tmp=q[rt][i];
dfs(tmp);
f1[rt]+=min(f1[tmp],min(f2[tmp],f3[tmp]));
f2[rt]+=min(f1[tmp],f2[tmp]);
cnt=min(cnt,f1[tmp]-min(f1[tmp],f2[tmp]));
f3[rt]+=min(f1[tmp],f2[tmp]);
}
f2[rt]+=cnt;
f1[rt]+=w[rt];
}
int main()
{
scanf("%d",&n);
for(int i=1,id,m;i<=n;i++)
{
scanf("%d",&id);
scanf("%d%d",&w[id],&m);
for(int j=1,r;j<=m;j++)
{
scanf("%d",&r);
q[id].push_back(r);
f[r]=id;
}
}
for(int i=1;i<=n;i++)
if(!f[i])
{
dfs(i);
ans=min(f1[i],f2[i]);
break;
}
printf("%d\n",ans);
return 0;
} -
02017-05-20 16:32:09@
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int n_r=1500,oo_max=0x3f3f3f3f,oo_min=0xcfcfcfcf; struct v_1 { int h,v; vector<int> s; }a[n_r+1]; int n,t_h; int f[n_r+1][3]; bool b[n_r+1]; void work_1(int now) { int v_0=0,v_1=0,v_2=0,min_x_1=oo_max; for (int i=1;i<a[now].s.size();i++) { work_1(a[now].s[i]); min_x_1=min(min_x_1,f[a[now].s[i]][2]-f[a[now].s[i]][1]); v_0+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]); v_1+=min(f[a[now].s[i]][1],f[a[now].s[i]][2]); v_2+=min(f[a[now].s[i]][0],min(f[a[now].s[i]][1],f[a[now].s[i]][2])); } v_1+=(min_x_1>0)?min_x_1:0; v_2+=a[now].v; f[now][0]=min(f[now][0],v_0); f[now][1]=min(f[now][1],v_1); f[now][2]=min(f[now][2],v_2); } int main() { while (~scanf("%d",&n)) { memset(b,0,sizeof(b)); for (int i=1;i<=n;i++) { int now,m; scanf("%d",&now); scanf("%d",&a[now].v); scanf("%d",&m); a[now].s.resize(m+1,0); for (int j=1;j<=m;j++) { scanf("%d",&a[now].s[j]); b[a[now].s[j]]=1; } } for (int i=1;i<=n;i++) if (b[i]==0) { t_h=i; break; } memset(f,oo_max,sizeof(f)); work_1(t_h); printf("%d\n",min(f[t_h][1],f[t_h][2])); } }
-
02017-04-05 22:15:38@
-
02016-06-29 18:04:56@
补充:
f[0][0][0]=f[0][0][1]=0;
f[0][1][0]=f[0][1][1]=INF; -
02015-10-10 19:20:19@
#include <cstdio>
#include <algorithm>
const int size=1505;
int n,m,x,i,j;
int son[size][size];
int tot[size],cost[size],flag[size];
int f[size][3];//0表示未被自己或儿子覆盖 1表示自己覆盖 2表示被儿子覆盖
using namespace std;
void init()
{
//freopen("palace.in","r",stdin);
//freopen("palace.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
f[i][1]=f[i][2]=1431655;
for (i=1;i<=n;i++)
{
scanf("%d",&x);
scanf("%d%d",&cost[x],&m);
for (j=1;j<=m;j++)
{
int p=++tot[x];
scanf("%d",&son[x][p]);
flag[son[x][p]]=1;//标识为1
}
}
}
void DP(int k)
{
f[k][1]=cost[k];
if (tot[k]==0) return;
for (int i=1;i<=tot[k];i++)
DP(son[k][i]);//往下枚举//用儿子更新自己的值
for (int i=1;i<=tot[k];i++)
{
int temp=son[k][i];
f[k][1]+=min(f[temp][0],min(f[temp][1],f[temp][2]));
}//自己覆盖,儿子随便怎么样都可以for (int i=1;i<=tot[k];i++)
{
int s=f[son[k][i]][1]; //自己覆盖的儿子的代价
for (int j=1;j<=tot[k];j++)
if (j!=i)
{
int temp=son[k][j];
s+=min(f[temp][1],f[temp][2]);
}
f[k][2]=min(f[k][2],s);
}//有一个儿子自己覆盖,其他随意(2/1),选一个最优值for (int i=1;i<=tot[k];i++)
f[k][0]+=f[son[k][i]][2];//自己的儿子被孙子覆盖,但自己未被覆盖
}
int main()
{
init();
for (i=1;i<=n;i++)
if (flag[i]==0) //如果标识为0,就是树根
{
DP(i);
printf("%d\n",min(f[i][1],f[i][2]));
break;
}
return 0;
} -
02015-10-07 12:09:40@
其实我写这道题的时候还不怎么了解<树形DP>,思路不很明朗,wrong answer了很多次……
###QAQ###不过那些0s的是咋搞的?
记录信息
评测状态 Accepted
题目 P1144 小胖守皇宫
递交时间 2015-10-07 11:54:53
代码语言 C++
评测机 VijosEx
消耗时间 24 ms
消耗内存 636 KiB
评测时间 2015-10-07 11:54:54
评测结果
编译成功测试数据 #0: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #1: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #2: Accepted, time = 1 ms, mem = 576 KiB, score = 14
测试数据 #3: Accepted, time = 1 ms, mem = 636 KiB, score = 14
测试数据 #4: Accepted, time = 8 ms, mem = 580 KiB, score = 14
测试数据 #5: Accepted, time = 6 ms, mem = 580 KiB, score = 14
测试数据 #6: Accepted, time = 6 ms, mem = 576 KiB, score = 14
Accepted, time = 24 ms, mem = 636 KiB, score = 98###代码
#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=2100000000;
int fir[1510];
int nxt[3020];
int link[3020];
int dp[1510][3];
/*dp[now][0]表示now点不安置守卫的最低花费,而是通过其子节点的守卫守卫,dp[now][1]表示now点安置守卫的最低花费,dp[now][2]表示now点不安置守卫,而是通过其父节点的守卫守卫的最低花费*/
int cost[1510]; //每个点的花费
int cnt;
void Link(int a,int b){nxt[++cnt]=fir[a];link[cnt]=b;fir[a]=cnt;}
void search(int now,int pre)
{
dp[now][1]=cost[now];
dp[now][2]=0;
int flag=inf;
for(int i=fir[now];i;i=nxt[i])
{
if(link[i]!=pre){
search(link[i],now);//先向下走,再从下往上DPdp[now][0]+=min(dp[link[i]][1],dp[link[i]][0]);
dp[now][1]+=min(dp[link[i]][1],min(dp[link[i]][2],dp[link[i]][0]));
dp[now][2]+=min(dp[link[i]][0],dp[link[i]][1]);//DP
if(dp[link[i]][1]<=dp[link[i]][0])flag=0;
if(flag&&dp[link[i]][1]-dp[link[i]][0]<flag){
flag=dp[link[i]][1]-dp[link[i]][0];
}
//特判,由于dp[now][0]只需要其某一个‘now的子节点’有守卫即可,需特殊处理
}
}dp[now][0]+=flag; //当now没有子节点时,dp[now][0]=inf;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b,k;
scanf("%d",&a);
scanf("%d",&cost[a]);
scanf("%d",&k);
while(k--){
scanf("%d",&b);
Link(a,b);
Link(b,a);
}
}
search(1,0);
printf("%d",min(dp[1][0],dp[1][1]));
} -
02015-09-18 13:38:51@
var son:array[0..1500,0..1500] of longint;
a:array[0..1500,0..2] of longint;
w,fa:array[0..1500] of longint;
n,m,i,j,k,l:longint;
function min(x,y,z:longint):longint;
begin
if x<=y then
if x<=z then exit(x);
if y<=x then
if y<=z then exit(y);
if z<=x then
if z<=y then exit(z);
end;
procedure dp(i:longint);
var r,o,l,m:longint;
begin
if son[i,0]=0 then begin a[i,1]:=w[i]; a[i,0]:=w[i]; exit; end;
for r:=1 to son[i,0] do
dp(son[i,r]);
a[i,1]:=w[i];
for r:=1 to son[i,0] do
a[i,1]:=a[i,1]+min(a[son[i,r],0],a[son[i,r],1],a[son[i,r],2]);
for r:=1 to son[i,0] do
a[i,2]:=a[i,2]+min(a[son[i,r],0],a[son[i,r],1],maxlongint);
m:=0; l:=maxlongint;
for r:=1 to son[i,0] do
if a[son[i,r],1]-a[son[i,r],0]<l then
begin
l:=a[son[i,r],1]-a[son[i,r],0];
m:=son[i,r];
end;
for r:=1 to son[i,0] do
if son[i,r]<>m then
a[i,0]:=a[i,0]+min(a[son[i,r],1],a[son[i,r],0],maxlongint)
else
a[i,0]:=a[i,0]+a[son[i,r],1];
end;
begin
read(n);
for i:=1 to n do
begin
read(j,w[j],m); son[j,0]:=m;
for l:=1 to m do
begin
read(son[j,l]);
fa[son[j,l]]:=j;
end;
end;
j:=1;
while fa[j]<>0 do
j:=fa[j];
dp(j);
writeln(min(maxlongint,a[j,0],a[j,1]));
end.
我想说DP思维都是很重要的,一开始错了,就难做了。 -
02015-08-15 20:16:00@
记录信息
评测状态 Accepted
题目 P1144 小胖守皇宫
递交时间 2015-08-15 20:06:13
代码语言 Pascal
评测机 VijosEx
消耗时间 0 ms
消耗内存 840 KiB
评测时间 2015-08-15 20:06:13
评测结果
编译成功Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
120 lines compiled, 0.1 sec , 29456 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 800 KiB, score = 14
测试数据 #1: Accepted, time = 0 ms, mem = 800 KiB, score = 14
测试数据 #2: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #3: Accepted, time = 0 ms, mem = 840 KiB, score = 14
测试数据 #4: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #5: Accepted, time = 0 ms, mem = 796 KiB, score = 14
测试数据 #6: Accepted, time = 0 ms, mem = 796 KiB, score = 14
Accepted, time = 0 ms, mem = 840 KiB, score = 98
代码
program P1144;
type
tNode=record
num:integer;
first,last:integer;
cost:integer;
end;var
size:integer;
child:array[1..1500] of integer;
node:array[1..1500] of tNode;
loc:array[1..1500] of integer;
answer:array[1..1500,0..2] of longint;
i,j,k,top,temp:integer;
function getRoot:integer;
var
i:integer;
flag:array[1..1500] of boolean;
begin
for i:=1 to top do
begin
flag[i]:=true;
end;
for i:=1 to top do
begin
flag[child[i]]:=false;
end;
for i:=1 to top do
begin
if flag[i] then
begin
exit(loc[i]);
end;
end;
end;
function min(a,b:longint):longint;
begin
if a<b then
begin
exit(a);
end;
exit(b);
end;function dp(this,flag:integer):longint;
var
i:integer;
sum:longint;
begin
if answer[this,flag]>=0 then
begin
exit(answer[this,flag]);
end;
if node[this].last<node[this].first then
begin
if flag<>0 then
begin
answer[this,flag]:=node[this].cost;
end
else
begin
answer[this,flag]:=0;
end;
exit(answer[this,flag]);
end;
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],0);
end;
dp:=sum+node[this].cost;
if flag<>2 then
begin
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],1);
end;
for i:=node[this].first to node[this].last do
begin
dp:=min(dp,sum-dp(loc[child[i]],1)+dp(loc[child[i]],2));
end;
end;
if flag=0 then
begin
sum:=0;
for i:=node[this].first to node[this].last do
begin
sum:=sum+dp(loc[child[i]],1);
end;
dp:=min(dp,sum);
end;
answer[this,flag]:=dp;
end;
begin
top:=1;
readln(size);
for i:=1 to size do
begin
read(j);
loc[j]:=i;
node[i].num:=j;
read(node[i].cost,j);
node[i].first:=top;
node[i].last:=top+j-1;
for k:=top to top+j-1 do
begin
read(temp);
child[k]:=temp;
end;
top:=top+j;
end;
for i:=1 to size do
begin
answer[i,0]:=-1;
answer[i,1]:=-1;
answer[i,2]:=-1;
end;
writeln(DP(getRoot,1));
end.
另answer[i,0]表示i号节点被他爸罩着,这个子树的最少花费,answer[i,1]表示第i个节点不被他爸罩着,他爸也不要求他罩的最少花费。answer[i,2]表示这个节点需要罩着他爸的最小花费。那么answer[i,0]=求和(answer[i的子树,1])
answer[i,1]=min(求和(answer[i的大部分子树,0])+answer[i剩下一个子树,2],求和(answer[i的子树,0])+cost[i]);
answer[i,2]=cost[i]+求和(answer[i的子树,0]) -
02014-10-17 21:30:15@
树形DP
dp(x,flag,flag)表示标号为x的节点是否选,而且他是否被父亲或自己看住。
dp(x,1,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,1));
dp(x,0,1)=Σmin(dp(ch[x][i],1,1),dp(ch[x][i],0,0));
dp(x,0,0)的转移复杂一点:从儿子中找出dp(ch[x][i],0,0)-dp(ch[x][t],1,1)最大的点,选中他来看住父亲,
dp(x,0,0)=dp(ch[x][t],1,1)+Σmin(dp(ch[x][i],0,0),dp(ch[x][i],1,1))(i!=t);(在此种情况下某种节点没有孩子,便返回INF)