张旭明:坚持做相同起事来差不多麻烦

近期进入了是因为国内自媒体“报大人”创建的微信群,群名叫“坚持做同码事-时间管理”,看名字知道凡是有关各种拖延症治愈系的总人口互动勉励群。

【SinGuLaRiTy-1015】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved.

群里出现如哪些坚持每天跑,坚持每日不扣电视机,坚持每天阅读,坚持每天创作,坚持每日早上,坚持每日不手淫,坚持每天反思,坚持每天读英语,坚持每日不扣美女,坚持每天免吃甜品,坚持每日减肥……由此看来,人们在“坚持”这起事上所面临的题目,远较自己设想的若多。

于有的题材:Time Limit:1s  |  Memory:256 MB

众人干什么花那么多的辰在“坚持”上。坚持,是坚持不懈正念,坚持做相同件正能量或者无开同码负能量的工作,都是内需意志支持的。见了每天阅读要坚持的,没见了睡懒觉需要咬牙的。

第一题:最长链(HDU 2196 Computer)

人们需要坚持,或许是盖想转吧。总觉得生命不可知还如此了,因此尝试做出改变。一件小事不克改一个人口,但是同样码小事又做就是会转一个口。小事又做,就需要坚持不懈才实施。而人口能免可知坚称,除了他自我的意志是否强大意外,就看他改动之愿是否明确。

问题叙述

被得一蔸有n个节点的扶植,求每个节点到外节点的尽要命距离。

一个丁改,也许是一个振奋,也许是一个有时候,但不管怎样,就是一个私的自身觉悟。这或多或少,千金难买。很多人口且生活不括,只见面发发牢骚,从不考虑如何做出行动。或许是恋人突然内暴富,聚会后心生怨闷,或许是观看人家起豪车泡洋妞,便骂是社会不公,却向没有尝试去改变,理想仅是漂亮而已。

输入

输入第一行是一个本来数n(n≤10000);

连下去 (n−1) 行描述:第i执行包含两单自数 ,
表示编号为i的节点连接至之节点编号与当下漫漫网线的尺寸..距离总长不会见过10^9.
每行中之有数单数字用空格隔开。

一个总人口想改了,并且做出改变的行为了,旁人便会见不解,问怎么而立马样子,以前这样不是格外好之吗?对呀,以前这样不是十分好呢?于是你还要转移回了老样子。或许旁人支持你改变,而且于了您不少反之建议,于是你仍别人的提议改变,发现改变起来十分痛,而且效果不十分。因为改变之希望是自外如果异,只有和谐承认的更动,改变才会,彻头彻尾,翻天覆地。

输出

出口包含n行.
第i行代表对离开编号为i的节点最远之节点和拖欠节点的偏离Si(1≤i≤n)。

支配要反了,坚持做同项事了,一开始不麻烦,难的是以为后底日子中依旧自若初见。想想也是,我的命受到尚当真没有一样宗工作是坚持了十年的,比如乒乓球、桌球、吉他、足球、篮球、排球、羽毛球、混球、跑步、写作、阅读。按照10000钟头理论,只要坚持十年,就会以很世界成为天才,成为学者。

样例数据

样例输入 样例输出

3

1 1

1 2

2

3

3

 

 

 

 

 

之所以,我一旦做出一些转移,而且早已以反。我以逐渐坚持做一些事先的工作,我期待举行十年,让其成为一种习惯。

数量规模

30% n≤100 

100% n≤10000

问题分析

即时道题是试验前一天课上言语的题材,如果我无记错的语应该是HDU
2196底原题。让自家鼓劲之是,尽管当时道题没有让布置上作业中,但自身昨天即令曾在HDU上AC了当下道题,再从一通代码也是一定的轻松,一种优越感油然而生……

下面,让咱来探视就道题的思路:对于其它一个节点M,我们得以去她最好远的接触之岗位分为两好像:①每当因为M为根节点的子树中,我们借而这个种情形下的最远距离吗maxdis_down;②以坐M为清节点的子树之外,我们借而这个种植情况下的绝远距离呢maxdis_up。显而易见的凡,此时夫点之极端远距离ans[M]就为max(maxdis_down,maxdis_up)。我们要看第二栽情况:maxdis_up=M到其父亲节点L的相距dis(M,L)+ans[L]。对斯,我们好定义一个dp[MAXN][3]的数组:

f[i][0]表示顶点为i的子树中,距离顶点i的最为远距离(对应第一栽情形);

f[i][1]表示i到那个父亲节点的距离+其大之极远距离(对应第二栽情景);

f[i][0]实际不需要DP,dfs就不过求解(本次dfs也求出次长距离);对于f[i][1],我们应用由父节点交子节点的方针。

假使发生同样L节点,它发生n个子节点,我们因而Vi来表示。

这,我们以要分开情况来讨论了:

①若Vi不是L的最好丰富路所经节点,有f[Vi][1]=dis(Vi,L)+max(f[L][0],f[L][1]);

②如果Vi是L的最丰富路所经节点,Vi的顶丰富路就是无能够更被算,我们尽管使“退而求其次”,使用第二长的路径Sec_dis,此时有f[Vi][1]=dis(Vi,L)+max(Sec_dis,f[L][1])。

<通过求树的直径解决>

塑造之直径是呀?就是在相同棵树上有的星星点点点中的卓绝远距离所经的门径。例如:

图片 1

每当该图中,树的直径,即距离太丰富之点滴沾内路径为:7、5、2、1、3、6

每当此地我们用用一个定论:对于自由一个扶植被的节点的话,距离其无限远之触发得是当下棵树的直径的星星点点只端点被之一个。【详见说明】

经之结论,我们即便得事先对片接触进展dfs求最远点,确定树的直径的点滴个端点,然后对培养被的点进行dfs求出长即可。

STD Code

#include<cstring>
#include<cstdio>
#include<algorithm>

#define MAXN 10010

using namespace std;

struct node_a
{
    int head;
}V[MAXN];

struct node_b
{
    int v;
    int w;
    int next;
}E[MAXN];

int top;

void init()
{
    memset(V,-1,sizeof(V));
    top=0;
}
void add_edge(int u,int v,int w)
{
    E[top].v=v;
    E[top].w=w;
    E[top].next=V[u].head;
    V[u].head=top++;
}
int dp[MAXN][3];
void dfs1(int u)
{
    int biggest=0,bigger=0;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v=E[i].v;
        dfs1(v);
        int tmp=dp[v][0]+E[i].w;
        if(biggest<=tmp)
        {
            bigger=biggest;
            biggest=tmp;
        }
        else if(bigger<tmp)
        {
            bigger=tmp;
        }
    }
    dp[u][0]=biggest;
    dp[u][1]=bigger;
}
void dfs2(int u)
{
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v=E[i].v;
        dp[v][2]=max(dp[u][2],dp[v][0]+E[i].w==dp[u][0] ? dp[u][1] : dp[u][0])+E[i].w;
        dfs2(v);
    }
}
int main()
{int n;
    scanf("%d",&n);
    init();
    for(int v=2;v<=n;v++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add_edge(u,v,w);
    }
    dfs1(1);
    dp[1][2]=0;
    dfs2(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",max(dp[i][0],dp[i][2]));
    }
    return 0;
}

亚书写:电视转播

题材叙述

一个电视机网络计划转播一摆重大之足球比赛。网络中的传输点和接收点(即用户)可以代表同样棵树。这株树的干净是一个传输点,它用转播比赛。树之叶节点是唯恐要接受这会较量的用户(他自然好选无扣比赛,这样便无须交款)。其他非根节点,非叶节点的中间节点也数量的中转站。将一个信号于一个传输点污染至另外一个传输点的费是加的。整个转播的花销就是各级一个传费用的总和。每一个用户(叶节点)都备提交得之钱来拘禁即会较量。电视网络商家只要控制是否要被这个用户提供电视信号。例如:给一个节点传输信息之花太要命,而异乐意的交账也颇少时,网络商家或者选择无吃他转播比赛。写一个主次,找到一个传输方案要尽多的用户能够顾转播比赛,且转播的费不越所有接信号用户的缴费。

输入

输入文件之首先履包含两单整数N和M(2<=N<=3000,1<=M<=N-1)。N,M表示分别表示树的节点数和思念见见比赛之用户数。树的彻底节点用1意味,中间节点的标号为2~N-M,用户的节点标号为N-M+1~N。接下来的N-M行表示传输点的音(依次是节点1,2……):
K A1 C1 A2 C2 …… Ak Ck
表示一个传输点将信号传于K个用户,每一个包含两个数A和C,A表示传输点或用户的节点号,C表示传输的花。最后一执行含有用户之多寡,有M个整数表示他们拘禁即会比赛愿意的付费。

输出

才一行包含一个平头,最深之用户数。

样例数据

样例输入 样例输出

5 3

2 2 2 5 3

2 3 2 4 3

3 4 2

2

5 3

2 2 2 5 3

2 3 2 4 3

4 4 2

3

9 6

3 2 2 3 2 9 3

2 4 2 5 2

3 6 2 7 2 8 2

4 3 3 3 1 1

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

题目分析

小心到了问题结尾处“找到一个传输方案要尽多的用户能够来看转播比赛,且转播的开销不跳所有接受信号用户之缴费”,这种熟悉的感觉到——一定是01背包问题,一定是这般的!用户就是一定给是品,传输费用一定于是代价,总交款就是背包的容量……于是,题目类型确定:DP+01背包问题。

概念一个f[MAXN][MAXN]数组,f[l][m]意味着:在根节点为l的子树中,将m个用户接入客户端所能够获取的最好老报酬。DP方程应该是较好理解的,树形DP套上一个01背包的笔触就是执行了:f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]-edge[i].w)

STD Code

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>

#define MAXN 3010
#define INF 0x3f3f3f3f

using namespace std;

struct node
{
    int v;
    int va;
};

vector <node> tu[MAXN];
int mo[MAXN],f[MAXN][MAXN],get[MAXN];
int n,m;

void add(int u,int v,int va)
{
    node p;
    p.v=v;
    p.va=va;
    tu[u].push_back(p);
}
void init()
{
    int tmp_1,tmp_2,tmp_3;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-m;i++)
    {
        scanf("%d",&tmp_1);
        for(int j=1;j<=tmp_1;j++)
        {
            scanf("%d%d",&tmp_2,&tmp_3);
            add(i,tmp_2,tmp_3);
        }
    }
    for(int i=n-m+1;i<=n;i++)
    {
        scanf("%d",&mo[i]);
    }
}
int dp(int x)
{
    if(x>n-m)
    {
        f[x][1]=mo[x];
        get[x]=1;
        return get[x];
    }
    for(unsigned int i=0;i<tu[x].size();i++)
    {
        get[x]+=dp(tu[x][i].v);
    }
    for(unsigned int i=0;i<tu[x].size();i++)
    {
        for(int j=get[x];j>=1;j--)
        {
            for(int k=min(j,get[tu[x][i].v]);k>=0;k--)
            {
                f[x][j]=max(f[x][j],f[tu[x][i].v][k]+f[x][j-k]-tu[x][i].va);
            }
        }
    }
    return get[x];
}
int main()
{
    init();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=-INF;
        }
    dp(1);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(f[1][i]>=0)
        {
            ans=max(ans,i);
        }
    }
    printf("%d",ans);
    return 0;
}

其三书写:叶子的颜料(CQOI 2009)

题目叙述

叫一样蔸m个结点的无根树,你可选择一个度数大于1的结点作为根本,然后为部分结点(根、内部结点和叶子均只是)着为黑色或白色。你的着色方案应该保证根结点到每个叶子的概括路径上且至少含有一个有色结点(哪怕是以此叶子本身)。

于每个叶结点u,定义c[u]呢于根结点到u的简单路径上最后一个死里逃生结点的颜色。给有每个c[u]的价值,设计着色方案,使得着色结点的个数尽量少。

输入

先是执行包含两个正整数m, n,其中n是纸牌的个数,m是结点总数。结点编号吧1,2,…,m,其中编号1,2,… ,n是纸牌。以下n行每行一个0还是1底平头(0代表黑色,1代表白色),依次为c[1],c[2],…,c[n]。以下m-1行每行两独整数a,b(1<=a < b <= m),表示结点a和b 有限度相连。

输出

唯有一个往往,即在质量结点数之尽小值。

样例数据

样例输入 样例输出

5 3

0

1

0

1 4

2 5

4 5

3 5

2

 

 

 

 

 

 

 

 

 

 

问题分析

在主题当中,题目并没有叫出树的干净节点,于是首先想到:第一步一定是找根……好吧,这个思路是错的,在末咱们会意识:无论选择啊一个节点作为根本,都未会见潜移默化答案和染状态。比如,当前增选一个节点x为根本来太优解,y为她有一个之儿子节点,x和y不会见同色——同色必然不也极优解,如果不同色,y转化为x的男,这样自然不会见潜移默化极其优解。

由于发现在一个子树中,不容许存在个别单颜色各异之接触未满足条件,我们得开展如下概念:
f[u][0]代表坐u为清节点的子树中不存在未满足条件的最好小染色节点数;

f[u][1]代表为u为清节点的子树中设有于染为0的节点不满足条件时的顶小染色节点数;

f[u][2]意味着因u为清节点的子树中是为染为1之节点不满足条件时的太小染色节点数;

对此:tmp_1=∑(f[v][1]);   tmp_2=∑(min(f[v][0],f[v][1]));  
tmp_3=∑(min(f[v][0],f[v][2]));

通过可得:f[u][0]=min(tmp_1,tmp_2+1,tmp_3+1);  
f[u][1]=min(tmp_2,tmp_3+1);   f[u][2]=min(tmp_2+1,tmp_3);

STD Code

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>

#define MAXN 10010
#define INF 0x3f3f3f3f

using namespace std;

vector <int> vec[MAXN];

int n,m;
int color,f[MAXN][10];
bool vis[MAXN];

void dp(int u)
{
    vis[u]=1;
    int tmp_1=0,tmp_2=0,tmp_3=0;
    bool flag=0;
    for(unsigned int i=0;i<vec[u].size();i++)
    {
        int v=vec[u][i];
        if(vis[v])
            continue;
        dp(v);
        tmp_1+=f[v][0];
        tmp_2+=min(f[v][0],f[v][1]);
        tmp_3+=min(f[v][0],f[v][2]);
        flag=1;
    }
    if(flag)
    {
        f[u][0]=min(tmp_1,min(tmp_2+1,tmp_3+1));
        f[u][1]=min(tmp_2,tmp_3+1);
        f[u][2]=min(tmp_2+1,tmp_3);
    }
}
int main()
{
    int u,v;
    scanf("%d%d",&n,&m);
    memset(f,INF,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&color);
        f[i][0]=1;
        f[i][color+1]=0;
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dp(n);
    printf("%d\n",f[n][0]);
    return 0;
}

 

Time : 2017-04-04