张旭明:坚持做同项事发生多麻烦

近年来进入了由于国内自媒体“报大人”创建的微信群,群名叫“坚持做一样项事-时间管理”,看名字知道凡是有关各种拖延症治愈系的丁相互勉励群。

【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