ここ数年のJAGの問題で最もひどいやつ。
問題の概念を理解するのが難しいだけ。説明なしにこんなこと書くのはどうかしてると思う。(本番では問題文が別の問題にすり替わっていてもっと酷かった)
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>g[210]; int p[210]; int z[210]; int v[110][210][210]; int val[110][210][210]; int sz=0; int dp[2][110][210][210]; int con[31000]; int A=15000; int calc(int at,int l,int r,int dep){ if(v[at][l][r])return val[at][l][r]; if(g[at].size()==0){ dp[0][at][l][r]=dp[1][at][l][r]=1; return val[at][l][r]=p[at]*dep; } int perm[10]; for(int i=0;i<g[at].size();i++){ perm[i]=i; } int len=g[at].size(); int best=z[0]; for(int i=0;i<len;i++){ best=max(best,-calc(g[at][i],0,sz-1,dep)); } val[at][l][r]=best; int r1=9999999; int r2=0; do{ int t1=0; int t2=0; int va=z[l]; int vb=z[r]; for(int i=0;i<len;i++){ int tmp=-calc(g[at][perm[i]],con[A-vb],con[A-va],dep); t1+=dp[0][g[at][perm[i]]][con[A-vb]][con[A-va]]; t2+=dp[1][g[at][perm[i]]][con[A-vb]][con[A-va]]; if(tmp>va){ va=tmp; } if(va>=vb)break; } r1=min(r1,t1); r2=max(r2,t2); }while(next_permutation(perm,perm+len)); dp[0][at][l][r]=r1; dp[1][at][l][r]=r2; v[at][l][r]=1; return val[at][l][r]; } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<a;i++){ int b;scanf("%d",&b); for(int j=0;j<b;j++){ int c;scanf("%d",&c);c--; g[i].push_back(c); } } for(int i=0;i<a;i++){ z[sz++]=p[i]; z[sz++]=-p[i]; } z[sz++]=11111; z[sz++]=-11111; std::sort(z,z+sz); for(int i=0;i<sz;i++){ con[z[i]+A]=i; } for(int i=0;i<a;i++)for(int j=0;j<sz;j++)for(int k=0;k<sz;k++){ dp[0][i][j][k]=dp[1][i][j][k]=-1; } calc(0,0,sz-1,1); //for(int i=0;i<a;i++)printf("%d\n",val[i][0][sz-1]); printf("%d %d\n",dp[0][0][0][sz-1],dp[1][0][0][sz-1]); }