洛谷P 2015二叉リンゴ樹&&洛谷P 2014選課樹形dp

3283 ワード

ツリーdp

参考ブログ:https://blog.csdn.net/kkkksc03/article/details/83018645
P 2015二叉リンゴの木
考え方:dfs+遡及+dp
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
const int MOD=100000007;
const int inf=0x3f3f3f3f;
const LL inff=0x3f3f3f3f3f3f3f3f;
const LL N=300005;
const LL M=5005;
#define MEF(x) memset(x,-1,sizeof(x))
#define ME0(x) memset(x,0,sizeof(x))
#define MEI(x) memset(x,inf,sizeof(x))
struct Edge
{
    int u,v,w,next;
}edge[205];
int cnt=0,first[105];
void init()
{
    cnt=0;
    MEF(first);
}
void add(int u,int v,int w)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=first[u];
    first[u]=cnt++;
}
int dp[105][105];//dp[i][j] i j 
void DP(int x,int fa,int q)
{
    for(int i=first[x];i!=-1;i=edge[i].next)
    {
        int lv=edge[i].v;
        if(lv==fa)
        {
            continue;
        }
        dp[lv][1]=edge[i].w;
        DP(lv,x,q);
        for(int j=q;j>=1;j--)
        {
            for(int k=0;k<=j;k++)
            {
                if((j!=1&&j!=k)||x==1)// ，j 
                {
                    dp[x][j]=max(dp[x][j],dp[lv][k]+dp[x][j-k]);// 
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    init();
    for(int n1=1,a,b,c;n1>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    ME0(dp);
    DP(1,0,q);
    cout<

P 2014選択科目
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
const int MOD=100000007;
const int inf=0x3f3f3f3f;
const LL inff=0x3f3f3f3f3f3f3f3f;
const LL N=300005;
const LL M=5005;
#define MEF(x) memset(x,-1,sizeof(x))
#define ME0(x) memset(x,0,sizeof(x))
#define MEI(x) memset(x,inf,sizeof(x))
struct Edge
{
    int u,v,w,next;
}edge[605];
int cnt,first[305];
void init()
{
    cnt=0;
    MEF(first);
}
void add(int u,int v,int w)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=first[u];
    first[u]=cnt++;
}
int dp[305][305];
void Dp(int x,int m)
{
    for(int i=first[x];i!=-1;i=edge[i].next)
    {
        int lv=edge[i].v;
        dp[lv][1]=edge[i].w;
        Dp(lv,m);
        for(int j=m;j>=1;j--)
        {
            for(int k=0;k<=j;k++)
            {
                if((j!=1&&j!=k)||x==0)
                {
                    dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[lv][k]);
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    init();
    for(int n1=1,a,b;n1<=n;n1++)
    {
        cin>>a>>b;
        add(a,n1,b);
    }
    Dp(0,m);
    cout<

[C++]BOJ 2667号:番号のみ

libgdxの基本的な使用--俳優と公演