【luogu1315】 观光公交[贪心]

noip2011 观光公交

有点难受QAQ

每次修改一条路\(i\) 它只会影响到达景点\(i+1\)以及它之后的连续的会出现”人等车“的情况的景点 若景点\(i+1\)之后出现一个景点是\(x\)"车等人"的情况那么这条路权值减少就会不影响到景点\(x\)及其之后的景点

那么每次贪心减去影响最大的那条边

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    rd(n),rd(m),rd(k);
    for(int i=1;ilas[i+1]) eff[i]=eff[i+1];
            else eff[i]=i+1;
        }
        int mx=0,pos=0;
        for(int i=1;imx) mx=sum[eff[i]]-sum[i],pos=i;
        ans-=mx,--d[pos];
    }
    printf("%lld",ans);
    return 0; 
}

你可能感兴趣的