BZOJ1117 POI 2009 소방소

팁: 1.욕심
코드 문제 해결 후:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int maxn = 1e5+1e3;
const int maxk = 25;
__inline int re() { int n; scanf("%d" , &n); return n; }

ll req[maxn][maxk];
ll has[maxn][maxk];

int res;
int n , s , k;
vector<int> g[maxn];

void range(int u , bool open = false)
{
    for(int i=0;i<=k;i++) for(int j=i;j>=0 && (open || j>=i-1);j--) 
    {
        ll cut = min(has[u][i] , req[u][j]);
        has[u][i] -= cut;
        req[u][j] -= cut;
        if(!has[u][i]) break;
    }
}

void dfs(int u , int fa)
{
    for(int i=0;iint v = g[u][i];
        if(v==fa) continue;
        dfs(v, u);
        for(int j=0;j< k;j++) req[u][j+1]+= req[v][j];
        for(int j=1;j<=k;j++) has[u][j-1]+= has[v][j];
    }

    req[u][0]++;

    ll urg = req[u][k] - has[u][k];
    if(urg>0)
    {
        int many = (urg+s-1)/s;
        has[u][k] += many*s;
        res+= many;
    }
    range(u);
}

int main(int argc, char *argv[]) {

    n = re(); s = re(); k = re();

    for(int i=1;iint a = re() , b = re();
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);
    range(1 , true);
    ll fin = 0;
    for(int i=0;i<=k;i++) fin+= req[1][i];
    res+= (fin+s-1)/s;

    printf("%d
" , res);

    return 0;
}

각 결점은 이 결점의 거리가 0~k인 것을 저장하고 덮어쓸 수 있으며 덮어쓸 수 있는 결점수도 있다.
만약 현재 결점 거리가 k인 덮어쓸 수 있는 결점수가 덮어쓸 수 있는 결점수보다 적다면 이 결점은 소방서가 필요하지 않을 수 없다는 것을 의미한다.우리는 그것을 좀 분배해 주었다. 마지막으로 우리는 뿌리 결점에 세워야 할 소방서를 계산하면 답이다.
각 결점의 두 양 사이에는 서로 상쇄해야 하지만, 완전히 마지막에 근결점을 계산한 것처럼 마음대로 상쇄하는 것은 아니다.우리는 i의 덮어쓸 수 있는 결점수로만 i와 i-1의 덮어쓸 수 있는 결점수를 상쇄합니다. 자세한 것은range를 보십시오.
왜 이렇게 해야 합니까? 만약 우리가 오픈이라는 변수를 제거한다면, 상쇄는 임의입니다. 우리는 덮어쓸 수 있는 거리가 큰 결점 할당액을 낭비할 수 있습니다.우리는 덮어씌울 수 없는 결점만 덮어씌운다. i와 i-1은 이 결점에 도착하면 아버지에게 덮어씌울 수 없다.
욕심의 증명에 관해서 때때로 우리는 이렇게 하는 것이 반드시 좋다는 것을 증명할 방법을 찾지 못하지만, 우리는 이것이 다른 결정보다 더 나쁘지 않다는 것을 설명할 수 있다.이 문제는 이렇다. 두 욕심이 많은 곳은 모두 이렇게 설명할 수 있다. 마지막으로 우리는 옳다. 단지 우리의 결정이 그다지 나쁘지 않기 때문이다.