낙곡2016 전략게임(나무DP)
1281 단어 ————DP————
전송문
[제목 분석]
이런 입문 DP가 어렵다고 생각했었는데.
n은 매우 작고 기억할 수 있기 때문에 직접 폭력적으로 검색하고 아버지가 넣었는지 여부를 열거한다. 만약에 넣지 않았다면 현재 지점에서 놓을 수밖에 없다. 그렇지 않으면 두 가지 모두 할 수 있다. 이렇게 dfs가 내려가서 답을 통계하면 된다.
[코드~] #include
using namespace std;
const int MAXN=2e3+10;
const int MAXM=4e3+10;
int n,cnt;
int a[MAXN],dp[MAXN][2];
int head[MAXN];
int nxt[MAXM],to[MAXM];
int Read(){
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void add(int x,int y){
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
cnt++;
}
int dfs(int u,int fa,int used){
if(dp[u][used]!=0x3f3f3f3f)
return dp[u][used];
int ret=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(v==fa)
continue;
if(!used){
ret+=dfs(v,u,1)+1;
}
else{
ret+=min(dfs(v,u,0),dfs(v,u,1)+1);
}
}
dp[u][used]=ret;
return ret;
}
int main(){
memset(head,-1,sizeof(head));
memset(dp,0x3f,sizeof(dp));
n=Read();
for(int i=1;i<=n;++i){
int x=Read(),k=Read();
for(int j=1;j<=k;++j){
int y=Read();
add(x,y),add(y,x);
}
}
dfs(0,-1,0);
dfs(0,-1,1);
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로곡 2285타 두더지 밀어주기?DP? 문제풀이 보고서
두더지는 구멍을 파는 것을 매우 좋아하는 동물이지만, 일정한 시간이 지나면 머리를 땅에 내밀어 바람을 쐬는 것을 좋아한다.이 특징에 따라 소는 두더지를 잡는 놀이를 만들었다.
n∗n의 격자에서 어떤 순간에 두더지는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
이런 입문 DP가 어렵다고 생각했었는데.
n은 매우 작고 기억할 수 있기 때문에 직접 폭력적으로 검색하고 아버지가 넣었는지 여부를 열거한다. 만약에 넣지 않았다면 현재 지점에서 놓을 수밖에 없다. 그렇지 않으면 두 가지 모두 할 수 있다. 이렇게 dfs가 내려가서 답을 통계하면 된다.
[코드~] #include
using namespace std;
const int MAXN=2e3+10;
const int MAXM=4e3+10;
int n,cnt;
int a[MAXN],dp[MAXN][2];
int head[MAXN];
int nxt[MAXM],to[MAXM];
int Read(){
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void add(int x,int y){
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
cnt++;
}
int dfs(int u,int fa,int used){
if(dp[u][used]!=0x3f3f3f3f)
return dp[u][used];
int ret=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(v==fa)
continue;
if(!used){
ret+=dfs(v,u,1)+1;
}
else{
ret+=min(dfs(v,u,0),dfs(v,u,1)+1);
}
}
dp[u][used]=ret;
return ret;
}
int main(){
memset(head,-1,sizeof(head));
memset(dp,0x3f,sizeof(dp));
n=Read();
for(int i=1;i<=n;++i){
int x=Read(),k=Read();
for(int j=1;j<=k;++j){
int y=Read();
add(x,y),add(y,x);
}
}
dfs(0,-1,0);
dfs(0,-1,1);
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로곡 2285타 두더지 밀어주기?DP? 문제풀이 보고서
두더지는 구멍을 파는 것을 매우 좋아하는 동물이지만, 일정한 시간이 지나면 머리를 땅에 내밀어 바람을 쐬는 것을 좋아한다.이 특징에 따라 소는 두더지를 잡는 놀이를 만들었다.
n∗n의 격자에서 어떤 순간에 두더지는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
using namespace std;
const int MAXN=2e3+10;
const int MAXM=4e3+10;
int n,cnt;
int a[MAXN],dp[MAXN][2];
int head[MAXN];
int nxt[MAXM],to[MAXM];
int Read(){
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void add(int x,int y){
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
cnt++;
}
int dfs(int u,int fa,int used){
if(dp[u][used]!=0x3f3f3f3f)
return dp[u][used];
int ret=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(v==fa)
continue;
if(!used){
ret+=dfs(v,u,1)+1;
}
else{
ret+=min(dfs(v,u,0),dfs(v,u,1)+1);
}
}
dp[u][used]=ret;
return ret;
}
int main(){
memset(head,-1,sizeof(head));
memset(dp,0x3f,sizeof(dp));
n=Read();
for(int i=1;i<=n;++i){
int x=Read(),k=Read();
for(int j=1;j<=k;++j){
int y=Read();
add(x,y),add(y,x);
}
}
dfs(0,-1,0);
dfs(0,-1,1);
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로곡 2285타 두더지 밀어주기?DP? 문제풀이 보고서두더지는 구멍을 파는 것을 매우 좋아하는 동물이지만, 일정한 시간이 지나면 머리를 땅에 내밀어 바람을 쐬는 것을 좋아한다.이 특징에 따라 소는 두더지를 잡는 놀이를 만들었다. n∗n의 격자에서 어떤 순간에 두더지는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.