快noip了就乱做一下历年的noip题目咯..
noip2014 飞扬的小鸟
其实这道题并不是很难，但是就有点难搞 听说男神错了一个小时..
就是$f_{i,j}$表示在第$i$个位置高度为$j$的时候最小点击次数
递推的话对于上升的情况只做一次，后面几次在后面再做..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 10010;
const int Maxm = 1010;
const int inf = 1e9;
int f[2][Maxm];
int n, m, K;
int l[Maxn], u[Maxn]; bool p[Maxn];
int X[Maxn], Y[Maxn];
int _min ( int x, int y ){ return x < y ? x : y; }
int main (){
int i, j, k;
scanf ( "%d%d%d", &n, &m, &K );
l[0] = 0; u[0] = m+1;
for ( i = 1; i <= n; i ++ ){ scanf ( "%d%d", &X[i], &Y[i] ); l[i] = 0; u[i] = m+1; }
for ( i = 1; i <= K; i ++ ){
int x;
scanf ( "%d", &x );
p[x] = true;
scanf ( "%d%d", &l[x], &u[x] );
}
int st = 0;
for ( i = 0; i <= m; i ++ ) f[st][i] = 0;
int num = 0;
for ( i = 1; i <= n; i ++ ){
st = st^1;
for ( j = 0; j <= m; j ++ ) f[st][j] = inf;
bool bk = false;
for ( j = l[i-1]+1; j < u[i-1]; j ++ ){
if ( f[st^1][j] == inf ) continue;
bk = true;
f[st][_min(j+X[i],m)] = _min ( f[st][_min(j+X[i],m)], f[st^1][j]+1 );
}
for ( j = 0; j <= m; j ++ ){
if ( f[st][j] != inf ) f[st][_min(j+X[i],m)] = _min ( f[st][_min(j+X[i],m)], f[st][j]+1 );
}
for ( j = l[i-1]+1; j < u[i-1]; j ++ ){
if ( f[st^1][j] == inf ) continue;
if ( j-Y[i] > l[i] && j-Y[i] < u[i] ) f[st][j-Y[i]] = _min ( f[st][j-Y[i]], f[st^1][j] );
}
if ( bk == false ){ printf ( "0\n%d\n", num-1 ); return 0; }
if ( p[i] == true ) num ++;
}
int ans = inf;
for ( i = 1; i <= m; i ++ ) ans = _min ( ans, f[st][i] );
printf ( "1\n%d\n", ans );
return 0;
}
noip2013 货车运输
就是裸的最大瓶颈树..
通俗点说就是最大生成树再用st表维护一下路径最小值..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 10010;
const int Maxm = 50010;
struct node {
int y, next, d;
}a[Maxn*2]; int first[Maxn], len;
void ins ( int x, int y, int d ){
len ++;
a[len].y = y; a[len].d = d;
a[len].next = first[x]; first[x] = len;
}
struct lnode {
int x, y, d;
}list[Maxm];
bool cmp ( lnode x, lnode y ){ return x.d > y.d; }
int n, m, q;
int fa[Maxn]; bool fw[Maxn];
int ff ( int x ){
if ( fa[x] == x ) return x;
return fa[x] = ff (fa[x]);
}
int minn[Maxn][15], fat[Maxn][15], dep[Maxn];
int _min ( int x, int y ){ return x < y ? x : y; }
void dfs ( int x, int f ){
fw[x] = true;
for ( int i = 1; i <= 14; i ++ ){
fat[x][i] = fat[fat[x][i-1]][i-1];
minn[x][i] = _min ( minn[x][i-1], minn[fat[x][i-1]][i-1] );
}
for ( int k = first[x]; k; k = a[k].next ){
int y = a[k].y;
if ( y == f ) continue;
fat[y][0] = x;
minn[y][0] = a[k].d;
dep[y] = dep[x]+1;
dfs ( y, x );
}
}
int lca ( int x, int y ){
int ret = 0x7fffffff;
if ( dep[x] < dep[y] ) swap ( x, y );
for ( int i = 14; i >= 0; i -- ){
if ( dep[fat[x][i]] >= dep[y] ){
ret = _min ( ret, minn[x][i] );
x = fat[x][i];
}
}
if ( x == y ) return ret;
for ( int i = 14; i >= 0; i -- ){
if ( fat[x][i] != fat[y][i] ){
ret = _min ( ret, minn[x][i] );
ret = _min ( ret, minn[y][i] );
x = fat[x][i]; y = fat[y][i];
}
}
return _min ( ret, _min ( minn[x][0], minn[y][0] ) );
}
int main (){
int i, j, k;
scanf ( "%d%d", &n, &m );
for ( i = 1; i <= m; i ++ ){
scanf ( "%d%d%d", &list[i].x, &list[i].y, &list[i].d );
}
sort ( list+1, list+m+1, cmp );
for ( i = 1; i <= n; i ++ ) fa[i] = i;
for ( i = 1; i <= m; i ++ ){
int fx = ff (list[i].x), fy = ff (list[i].y);
if ( fx != fy ){
fa[fy] = fx;
ins ( list[i].x, list[i].y, list[i].d );
ins ( list[i].y, list[i].x, list[i].d );
}
}
for ( i = 1; i <= n; i ++ ){
if ( fw[i] == false ){ dep[i] = 1; dfs ( i, 0 ); }
}
scanf ( "%d", &q );
for ( i = 1; i <= q; i ++ ){
int x, y;
scanf ( "%d%d", &x, &y );
int fx = ff (x), fy = ff (y);
if ( fx != fy ) printf ( "-1\n" );
else printf ( "%d\n", lca ( x, y ) );
}
return 0;
}
原文：http://www.cnblogs.com/darklove/p/6063721.html