送分题

1.没有上司的舞会

很久之前写的了，然后看了一下当时的代码感觉有点迷？

似乎是把可以一起选的装成一个背包，然后硬生生用背包做，状态加一维表示这个级别的选没选，没选才可以选它的儿子级别的。

其实没怎么看，就口胡一下。

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           const int maxn=6000+299;using namespace std;int n,a[maxn],first[maxn],next[maxn],to[maxn],x,y;int bag[maxn],ncnt;int f[maxn][2];bool rudu[maxn];int max(int a,int b){    return a>b?a:b;}int ecnt=0;int add(int u,int v){    next[++ecnt]=first[v];first[v]=ecnt;to[ecnt]=u;} void makebag(int boss,int cnt){    for(int i=first[boss];i<6299;i=next[i])    {        bag[cnt]+=a[to[i]];        if(cnt>ncnt) ncnt=cnt;        makebag(to[i],cnt+1);    }}int main(){    scanf("%d",&n);    memset(first,127/3,sizeof(first));    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);    for(int i=1;i
           
            >tmp1>>tmp2; int boss=0; for(int i=1;i<=n;i++) if(rudu[i]==0)boss=i; first[6290]=6290;next[6290]=6300; to[6290]=boss; makebag(6290,1); for(int i=1;i<=ncnt;i++) { f[i][1]=max(f[i-1][0]+bag[i],f[i-1][0]); f[i][0]=max(f[i-1][0],f[i-1][1]); } printf("%d",max(f[ncnt][0],f[ncnt][1])); return 0;}
           
          
         
        
       
      

 

2.vijos 加分二叉树

难度为2，发现自己不会做。。

愉快地瞄一眼题解，发现是记忆化搜索啊，然后就豁然开朗了。

记忆化搜索大发好。跟着套路走。

//Twenty#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn=31;int a[maxn],n,dp[maxn][maxn],lc[maxn],rc[maxn];int dfs(int l,int r) { if(l==r) dp[l][r]=a[l]; if(dp[l][r]) return dp[l][r]; for(int i=l;i<=r;i++) { int ll=(i==l?1:dfs(l,i-1)),rr=(i==n?1:dfs(i+1,r)); dp[l][r]=max(dp[l][r],ll*rr+a[i]); } return dp[l][r];}void print(int l,int r) { if(l==r) {printf("%d ",l); return;} for(int i=l;i<=r;i++) { int ll=(i==l?1:dfs(l,i-1)),rr=(i==n?1:dfs(i+1,r)); if(dp[l][r]==ll*rr+a[i]){ print(i,i); if(i!=l) print(l,i-1); if(i!=r) print(i+1,r); break; } }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); printf("%d\n",dfs(1,n)); print(1,n); return 0;}
             
            
           
          
         
        
       
      

 

3.

树形dp基础题，f[i][j]表示在i这个点我和我的子树联通块大小为j最少砍几条边。　　

转移的时候，到下一个子树时上一个子树所有答案先++（此树直接砍掉不贡献答案），再继续dp。

注意更新答案时，如果不是跟答案还有+1（砍掉我和我父亲的），不然洛谷会挂四个点QAQ

马上就Noip了我还只能做这种水题QAQ 还挂

//Twenty#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              typedef long long LL;using namespace std;const int N=201;int ans,dp[N][N],n,p;template
              
                void read(T &x) { char ch=getchar(); T f=1; x=0; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[N],nxt[N<<1],to[N<<1];void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;}void dfs(int x,int fa) { dp[x][1]=0; for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) { int y=to[i]; dfs(y,x); for(int j=p;j>=1;j--) { dp[x][j]++; for(int k=0;k
              
             
            
           
          
         
        
       
      
     

 

4.　

树形dp水题。

dp[i][j]表示在i这个点，在我和我的儿子中选了j门课的最大学分。注意转移时若i!=0自己必须选，所以枚举我儿子选的课必须小于我和我儿子选的所有课，而i==0时则小于等于都ok。

//Twenty#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              typedef long long LL;using namespace std;const int maxn=307;int n,m,dp[maxn][maxn],f[maxn],v[maxn];template
              
                void read(T &x) { char ch=getchar(); T f=1; x=0; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[maxn],nxt[maxn],to[maxn],ans;void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;}void dfs(int x) { dp[x][1]=v[x]; for(int i=fir[x];i;i=nxt[i]) { int y=to[i]; dfs(y); for(int j=m;j>=0;j--) for(int k=0;k<=(j-(x!=0));k++) dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[y][k]); } ans=max(ans,dp[x][m]);}void work() { dfs(0); printf("%d\n",ans);}void init() { read(n); read(m); for(int i=1;i<=n;i++) { read(f[i]); read(v[i]); add(f[i],i); }}int main() {#ifdef DEBUG freopen(".in","r",stdin); freopen(".out","w",stdout);#endif init(); work(); return 0;}
              
             
            
           
          
         
        
       
      
     

 

5.

又是树形dp水题。。

跟上面两个没啥差，还是最简单的。没啥可说了。

好水呀。。

//Twenty#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              typedef long long LL;using namespace std;const int maxn=100;int n,m,dp[maxn][maxn];template
              
                void read(T &x) { char ch=getchar(); T f=1; x=0; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],ans;void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}void dfs(int x,int fa) { for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) { int y=to[i]; dfs(y,x); for(int j=m;j>=0;j--) for(int k=0;k
              
             
            
           
          
         
        
       
      
     

 

因为找题的时候已经知道是二分了，一开始有点懵逼，然后突然想起世界上有种叫01分数规划的东西，然后树形dp就ok了。

这个看起来是n^3的dp实际上似乎是n^2的，然后bzoj加了一组数据后先sz[x]+=sz[y]再转移就过不了了，然后改一下就卡过了。

//Twenty#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define eps 1e-4typedef long long LL;using namespace std;const int maxn=2507;int n,m,b[maxn],a[maxn],f[maxn];double l,r=10000,dp[maxn][maxn];template
              
                void read(T &x) { char ch=getchar(); T f=1; x=0; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}int ecnt,fir[maxn],nxt[maxn],to[maxn],sz[maxn];void add(int u,int v) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; }void dfs(int x,double now) { if(x) dp[x][1]=(double)a[x]-(double)b[x]*now; if(x!=0) sz[x]=1; else sz[x]=0; dp[x][0]=0; for(int i=fir[x];i;i=nxt[i]) { int y=to[i]; dfs(y,now); for(int j=sz[x];j>=(x!=0);j--) { for(int k=0;k<=sz[y];k++) dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[y][k]); } sz[x]+=sz[y]; }}void work() { while(r-l>=eps) { double mid=(l+r)/2; memset(dp,0xc2,sizeof(dp)); dfs(0,mid); if(dp[0][m]>=eps) l=mid; else r=mid; } printf("%.3lf\n",l);}void init() { read(m); read(n); for(int i=1;i<=n;i++) { read(b[i]); read(a[i]); read(f[i]); add(f[i],i); }}int main() {#ifdef DEBUG freopen(".in","r",stdin); freopen(".out","w",stdout);#endif init(); work(); return 0;}
              
             
            
           
          
         
        
       
      
     

 

中等题

dp[i][j][k]代表i点和它的子树共分配j的时间，k次下去没有回来的最大得分。

 

至底往上贪心。

考虑一条链上去只要能管得到肯定往上放比较优，每次从下到上再在上面考虑下面的情况。

g[x][i]表示x点往下i的距离的位置还需要多少灭火器，f[x][i]表示x点往下i的距离的位置有多少没用的灭火器。

 

考虑每条边对答案的贡献是边两边的黑点数乘积加白点数乘积乘以边长。所以我们只要知道一个点的某个子树中的黑点数就可以算它到子树这条边的贡献。

 

玄学树dp