DP相关题解

Tree of Tree （树形DP）

VJ链接：https://vjudge.net/problem/ZOJ-3201

大概写了一下树形DP入门题，入门题套路都在搜到叶子节点然后处理子树。。

确定DP转移方程时注意b要正序a要倒序，

如k=5,假设这时算到第i(>1)个子树，此时dp[u][5]中存的是利用其他子树构造出的最大树，

利用此子节点更新父节点（父节点中“腾”出位置给该子树），

如果a正序，那么dp[u][2+b]=dp[u][2]+dp[v][b]时，dp[u][2]（已经计算过）值代表的树中可能已经有该子节点，此时dp[v][b]中也包含该子节点，明显是错误的状态。

如果a 倒序，dp[u][2+b]=dp[u][2]+dp[v][b]，此时dp[u][2]（未计算过）仍然表示由其他子节点构成的树，用该树再加子树才是正确状态。

发现写码迷的地方写出来题解就很清楚了。）

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,k,tot;
int a[111];
//
int head[111];
struct IN
{
    int v;
    int nex;
    IN(){}IN(int vv,int nn){v=vv,nex=nn;}
}edge[MAXN];
int dp[111][111];
int ans;
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].v;
        if(v==fa) continue;
        dfs(v,x);
        for(int a=k-1;a>0;a--)
            for(int b=1;a+b<=k;b++)
                dp[x][a+b]=max(dp[x][a+b],dp[x][a]+dp[v][b]);
    }
    ans=max(ans,dp[x][k]);
}

int main()
{
    while(~s2(n,k))
    {
        tot=0;mem(head,0);
        ans=0;mem(dp,0);
        for(int i=1;i<=n;i++)
            s1(dp[i][1]);
        for(int i=1;i<n;i++)
        {
            int u,v;s2(u,v);u++;v++;
            edge[++tot]=IN(v,head[u]);head[u]=tot;
            edge[++tot]=IN(u,head[v]);head[v]=tot;
        }
        dfs(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

Dividing the Path （单调队列优化）

VJ链接：https://vjudge.net/problem/POJ-2373

类似这样的转移方程可以用到单调队列： f[i]=max(f[j])+w[i]（其中max中的f[i]有固定范围）

大致流程：

1、先删掉前面超出范围的队头。
2、利用队头转移。
3、将这个数和队尾比较，若队尾不比它优，就删掉队尾，直到队列为空或队尾比它优。最后将它加进队尾。

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,l,a,b;
int mp[MAXN];
int dp[MAXN];//0到i位置的最小数目，i应为偶数
//dp[i]=min(dp[j])+1,j在(i-2*B,i-2*A)之间;
//i,j位置无奶牛，i>=2*a
int que[MAXN];//存储下标
int main()
{
    s2(n,l);s2(a,b);
    for(int i=0;i<=l;i++)
    {mp[i]=0;dp[i]=INF;}
    for(int i=0,s,e;i<n;i++)
    {
        s2(s,e);
        for(int j=s+1;j<e;j++) //注意端点重复不算重复
            mp[j]=1;
    }
    dp[0]=0;
    int head=0,tail=0;
    for(int i=2*a;i<=l;i+=2)
    {
        while (head<tail && que[head]<i-2*b)//超过范围
            head++;
        while (head<tail && dp[que[tail-1]]>=dp[i-2*a])//答案更优
            tail--;
        que[tail++]=i-2*a;
        if (dp[que[head]]!=INF&&!mp[i])
            dp[i]=dp[que[head]]+1;
    }
    if(dp[l]==INF) dp[l]=-1;
    printf("%d\n",dp[l]);
    return 0;
}