ztx's Blog

/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;

template<typename T>
inline void read(T& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

typedef long long ll ;

#include <cstring>

#define  maxn  105LL
#define  maxm  25LL
#define  maxd  10010LL
#define  info  0x7f7f7f7f7f7f7f7fLL
/* maxd 坑死人 = = */

int n , m , u , v ;
ll K ;
ll f[maxn] = {0} ;
ll length[maxn][maxn] = {0} ;

ll map[maxm][maxm] = {0} ;
ll dis[maxm] = {0} ;
bool inq[maxm] = {0} ;
int cont_time[maxd][3] = {0} ;
bool cont[maxm] = {0} ;

#define  sizeque  100LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; }
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; }
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }

void SPFA(int start , int end) {
    memset(cont , 0 , sizeof cont) ;
    memset(dis , 0x7f , sizeof dis) ; clear() ;
    for (u = 1 ; u <= cont_time[0][0] ; u ++ ) {
        if (cont_time[u][1]>end || cont_time[u][2]<start) continue ;
        else cont[cont_time[u][0]] = true ;
    }
    push_back(1) ; inq[1] = true ; dis[1] = 0 ;
    while (!empty()) {
        u = front() , pop_front() ; inq[u] = false ;
        for (v = 1 ; v <= m ; v ++ ) {
            if (map[u][v]==info || cont[v]) continue ;
            if (dis[v] > dis[u]+map[u][v]) {
                dis[v] = dis[u]+map[u][v] ;
                if (!inq[v]) {
                    inq[v] = true ;
                    if (!empty() && dis[v]<dis[front()]) push_front(v) ;
                    else push_back(v) ;
                }
            }
        }
    }
    if (dis[m] == info) length[start][end] = -1 ;
    else length[start][end] = dis[m] ;
}

int i , j ;
ll tmp ;
int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    read(n) , read(m) , read(K) , read(i) ;
    memset(map , 0x7f , sizeof map) ;
    while (i -- ) {
        read(u) , read(v) , read(tmp) ;
        if (map[u][v] > tmp) { map[u][v] = map[v][u] = tmp ; }
    }
    read(cont_time[0][0]) ;
    for (i = 1 ; i <= cont_time[0][0] ; i ++ ) {
        read(cont_time[i][0]) , read(cont_time[i][1]) , read(cont_time[i][2]) ;
    }
    for (i = 1 ; i <= n ; i ++ )
        for (j = i ; j <= n ; j ++ )
            SPFA(i , j) ;
    memset(f , 0x7f , sizeof f) ;
    f[0] = -K ;
    for (i = 1 ; i <= n ; i ++ ) {
        for (j = 0 ; j < i ; j ++ ) {
            if (f[j]==info || length[j+1][i]<0) continue ;
            tmp = f[j]+(ll)K+(ll)length[j+1][i]*(ll)(i-j) ;
            if (tmp < f[i]) f[i] = tmp ;
        }
    }
    printf("%lld\n", f[n] ) ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [FJOI2007]轮状病毒
* ALG    : dp
* CMT    : 打表,怎么推出来的自行百度 = =
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [FJOI2007]轮状病毒
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#include <iostream>

using namespace std ;

string ans[102] = {
"= =",
"1",
"5",
"16",
"45",
"121",
"320",
"841",
"2205",
"5776",
"15125",
"39601",
"103680",
"271441",
"710645",
"1860496",
"4870845",
"12752041",
"33385280",
"87403801",
"228826125",
"599074576",
"1568397605",
"4106118241",
"10749957120",
"28143753121",
"73681302245",
"192900153616",
"505019158605",
"1322157322201",
"3461452808000",
"9062201101801",
"23725150497405",
"62113250390416",
"162614600673845",
"425730551631121",
"1114577054219520",
"2918000611027441",
"7639424778862805",
"20000273725560976",
"52361396397820125",
"137083915467899401",
"358890350005878080",
"939587134549734841",
"2459871053643326445",
"6440026026380244496",
"16860207025497407045",
"44140595050111976641",
"115561578124838522880",
"302544139324403592001",
"792070839848372253125",
"2073668380220713167376",
"5428934300813767249005",
"14213134522220588579641",
"37210469265847998489920",
"97418273275323406890121",
"255044350560122222180445",
"667714778405043259651216",
"1748099984655007556773205",
"4576585175559979410668401",
"11981655542024930675232000",
"31368381450514812615027601",
"82123488809519507169850805",
"215002084978043708894524816",
"562882766124611619513723645",
"1473646213395791149646646121",
"3858055874062761829426214720",
"10100521408792494338631998041",
"26443508352314721186469779405",
"69230003648151669220777340176",
"181246502592140286475862241125",
"474509504128269190206809383201",
"1242282009792667284144565908480",
"3252336525249732662226888342241",
"8514727565956530702536099118245",
"22291846172619859445381409012496",
"58360810951903047633608127919245",
"152790586683089283455442974745241",
"400010949097364802732720796316480",
"1047242260609005124742719414204201",
"2741715832729650571495437446296125",
"7177905237579946589743592924684176",
"18791999880010189197735341327756405",
"49198094402450621003462431058585041",
"128802283327341673812651951847998720",
"337208755579574400434493424485411121",
"882823983411381527490828321608234645",
"2311263194654570182037991540339292816",
"6050965600552329018623146299409643805",
"15841633607002416873831447357889638601",
"41473935220454921602871195774259272000",
"108580172054362347934782139964888177401",
"284266580942632122201475224120405260205",
"744219570773534018669643532396327603216",
"1948392131377969933807455373068577549445",
"5100956823360375782752722586809405045121",
"13354478338703157414450712387359637585920",
"34962478192749096460599414575269507712641",
"91532956239544131967347531338448885552005",
"239636390525883299441443179440077148943376",
"627376215338105766356982006981782561278125",
"1642492255488433999629502841505270534891001"
} ;

int n ;

int main() {
	#define READ
	#ifdef  READ
		freopen("bzoj_1002.in" ,"r",stdin ) ;
		freopen("bzoj_1002.out","w",stdout) ;
	#endif
//	ios::sync_with_stdio(false) ;
	cin >> n ;
	cout << ans[n] ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}
/*

HP fe[101] ;
HP fo[101] ;
HP ans[101] ;
  	fe[1] = 1 ; fe[2] = 4 ;
	fo[1] = 1 ; fo[2] = 3 ;
	fo[0] = 3;
	fe[0] = 5 ;
	int n = 100 ;
	int m = 55 ;
	for (int i = 3 ; i <= m ; i ++ ) {
		fe[i] = fe[i-1]*fo[0];
		fe[i] = fe[i]-fe[i-2] ;
		fo[i] = fo[i-1]*fo[0];
		fo[i] = fo[i]-fo[i-2] ;
	}
	int k ;
	for (int i = 1 ; i <= 100 ; i ++ ) {
		if (i&1) {
			k = (i+1)>>1 ;
			ans[i] = fo[k]*fo[k]*fe[0] ;
		}
		else {
			k = (i>>1)+1 ;
			ans[i] = fe[k]*fe[k] ;
		}
	}
	for (int i = 1 ; i <= 100 ; i ++ ) {
		cout<<"\""<<ans[i]<<"\","<<endl;
	}

*/

/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH ;
inline void read(int& ret) {
    ret = 0 ; while (CH=getchar() , CH<'!') ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

#define  maxn  1010LL
#define  maxw  6010LL

int n , ans = 0 , answ = 0 , wei[maxn] , lim[maxn] ;
int f[maxn][maxw] = {0} ;
int pre[maxn][maxw] = {0} ;

void PrintfPath(int now , int w) {
	if (now>n || w<=0) return ;
	PrintfPath(now+1 , pre[now][w]) ;
	if (pre[now][w] != w) printf("%d\n",now) ;
}

int i , w ;
int main() {
	#define READ
	#ifdef  READ
		freopen("boxes.in" ,"r",stdin ) ;
		freopen("boxes.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ ) {
		read(wei[i]) , read(lim[i]) ;
		f[i][wei[i]] = 1 ;
	}
	for (i = n ; i > 0 ; i -- )
		for (w = 6000 ; w > 0 ; w -- ) {
			f[i][w] = f[i+1][w] ;
			pre[i][w] = w ;
			if (w<=lim[i] && f[i][w+wei[i]]<f[i+1][w]+1) {
				f[i][w+wei[i]] = f[i+1][w]+1 ;
				pre[i][w+wei[i]] = w ;
			}
		}
	for (w = 6000 ; w > 0 ; w -- )
		if (f[1][w] > ans) ans = f[1][w] , answ = w ;
	printf("%d\n", ans );
	PrintfPath(1 , answ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}