NC200325. 神经冲动
描述
输入描述
第一行一个整数n，表示生物的神经系统一共有n个神经节点，每个节点初始均为静息状态。接下来一行，共n-1个数描述了其神经结构，第i个数字表示i+1个神经节点的父节点编号。接下来一行，共n个数，表示每个神经节点的目标状态（1表示兴奋，0表示静息）
输出描述
一个整数，表示最少需要的时间。
如果永远不可能达成目标，则这种操作是不可完成的，输出“frog”（不含引号）
示例1
输入:
7 1 2 3 3 3 4 1 0 0 1 0 1 1
输出:
3
说明:
第一秒刺激7号节点，神经上的兴奋情况：0 0 0 0 0 0 1C++(g++ 7.5.0) 解法, 执行用时: 44ms, 内存消耗: 988K, 提交时间: 2023-01-17 10:56:46
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)
using namespace std;
const int N=1<<4;
int n,fa[N],target,now,dp[N][N],flag[1<<N];
void dfs(int x,int tag)
{
if(now==target)
{
cout<<tag;
exit(0);
}
if(x==tag)
return;
for(int i=1;i<=n;++i)
{
now^=dp[i][tag-x];
if(x<flag[now])
{
flag[now]=x;
dfs(x+1,tag);
}
now^=dp[i][tag-x];
}
dfs(x+1,tag);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=2;i<=n;++i)
cin>>fa[i];
for(int i=1,x;i<=n;++i)
{
cin>>x;
target<<=1;
target|=x;
}
for(int i=1;i<=n;++i)
{
int x=i;
for(int j=1;j<=n;++j)
{
if(x)
dp[i][j]=dp[i][j-1]|(1<<(n-x));
else
dp[i][j]=dp[i][j-1];
x=fa[x];
}
}
for(int k=0;k<=n;++k)
{
memset(flag,10,sizeof flag);
dfs(0,k);
}
puts("frog");
return 0;
}
C++14(g++5.4) 解法, 执行用时: 10ms, 内存消耗: 1772K, 提交时间: 2020-03-17 20:31:42
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mx,n,i,j,k,x,s,T,fa[10010],f[50][100010],g[50][100];
int main(){
scanf("%d",&n);
for(i=2;i<=n;i++){
scanf("%d",&fa[i]);
}
for(i=1;i<=n;i++){
scanf("%d",&x);
T+=(1<<i-1)*x;
}
if(!T)return puts("0"),0;
for(i=1;i<=n;i++){
x=i;s=0;
for(j=1;j<=n*2;j++){
if(x)s|=1<<x-1;
g[i][j]=s;
x=fa[x];
}
}
f[0][0]=1;
mx=1<<n;
for(i=1;i<=n*2;i++){
for(j=0;j<mx;j++)if(f[i-1][j]){
f[i][j]=1;
for(k=1;k<=n;k++)f[i][j^g[k][i]]=1;
}
if(f[i][T])return printf("%d",i),0;
}
}
C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 1900K, 提交时间: 2020-03-08 14:16:14
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mx,n,i,j,k,x,s,T,fa[10010],f[50][100010],g[50][100];
int main(){
scanf("%d",&n);
for(i=2;i<=n;i++){
scanf("%d",&fa[i]);
}
for(i=1;i<=n;i++){
scanf("%d",&x);
T+=(1<<i-1)*x;
}
if(!T)return puts("0"),0;
for(i=1;i<=n;i++){
x=i;s=0;
for(j=1;j<=n*2;j++){
if(x)s|=1<<x-1;
g[i][j]=s;
x=fa[x];
}
}
f[0][0]=1;
mx=1<<n;
for(i=1;i<=n*2;i++){
for(j=0;j<mx;j++)if(f[i-1][j]){
f[i][j]=1;
for(k=1;k<=n;k++)f[i][j^g[k][i]]=1;
}
if(f[i][T])return printf("%d",i),0;
}
}