张旭明:坚持做相同桩事时有发生差不多麻烦

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

【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