萌新第一次打hihoCoder的比赛有点慌
T1
T1并不是特别难想到dp就好做了
显而易见的是一个01背包问题
Code：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF=233333; int n,m,i,j,k,f[3005],son[3005],x; int main() { cin>>n;memset(son,0,sizeof son); for (int i=1;i<n;i++) cin>>x,son[x]++; memset(f,INF,sizeof f);f[0]=0; for (int i=1;i<=n;i++) for (int j=n;j>=son[i];j--) f[j]=min(f[j],f[j-son[i]]+1); for (int i=0;i<n;i++) { if (f[i]>n) cout<<-1<<" "; else cout<<f[i]<<" "; } return 0; }
T2
T2的话是一个区间dp的题
可以抽象成在某一棵子树上维护方案数
在维护两个数组f,g
g[i]表示这棵子树到i点的方案数
f[i][j]表示[i,j]为一颗子树的方案数
Code：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 998244353 using namespace std; long long n,g[1005],f[505][505]; char A[3005],B[3005]; int main() { cin>>n;getchar();gets(A+1);gets(B+1); for (int i=1;i<=n;i++) if (A[i]!=‘1‘) f[i][i]=1; for (int i=n-1;i>=1;i--) if (A[i]!=‘0‘) { for (int j=i;j<=n;j++) g[j]=0; g[i]=1; for (int j=i+1;j<=n;j++) for (int k=j;k<=n;k++) { if (B[j]!=‘0‘) g[k]=(g[k]+(long long)f[j][k]*g[j-1])%MOD; if (B[j]!=‘1‘) f[i][k]=(f[i][k]+(long long)f[j][k]*g[j-1])%MOD; } } if (B[1]==‘1‘) cout<<0<<endl; else cout<<f[1][n]<<endl; }
T3，T4尚未写好，以后再更
原文：http://www.cnblogs.com/tantanshuangjian/p/6224064.html