首页 > 代码库 > zoj 2972 - Hurdles of 110m
zoj 2972 - Hurdles of 110m
题目:110米栏,运动员能够用三种状态跑,1状态耗体力且跑得快,2状态不消耗体力,3状态恢复体力且跑得慢。
体力上限是M,且初始满体力,如今想知到最小的时间跑全然程。
分析:dp,全然背包。题目是一个物品体积可能为负数的背包,求背包就可以。
只是,由于物品体积可能是负数,所以无论哪个方向背包都有后效性,直接用二维避免后效性。
转移方程:F(i,j)= min(F(i-F1,j)+ T1,F(i-1,j)+ T2,F(i+F2,j)+T3)。
说明:(2011-09-19 01:23)。
#include <iostream> #include <cstdlib> using namespace std; int F[ 111 ][ 111 ]; int T1[ 111 ]; int T2[ 111 ]; int T3[ 111 ]; int F1[ 111 ]; int F2[ 111 ]; int dp( int N, int M ) { for ( int i = 0 ; i <= N ; ++ i ) for ( int j = 0 ; j <= M ; ++ j ) F[ i ][ j ] = 0xffffff; for ( int i = 0 ; i <= M ; ++ i ) F[ 0 ][ i ] = 0; for ( int i = 1 ; i <= N ; ++ i ) { /* 第一状态 */ for ( int j = F1[ i ] ; j <= M ; ++ j ) if ( j <= M && F[ i ][ j-F1[ i ] ] > F[ i-1 ][ j ] + T1[ i ] ) F[ i ][ j-F1[ i ] ] = F[ i-1 ][ j ] + T1[ i ]; /* 第二状态 */ for ( int j = 0 ; j <= M ; ++ j ) if ( F[ i ][ j ] > F[ i-1 ][ j ] + T2[ i ] ) F[ i ][ j ] = F[ i-1 ][ j ] + T2[ i ]; /* 第三状态 */ for ( int j = 0 ; j <= M ; ++ j ) if ( F[ i ][ min(j+F2[ i ],M) ] > F[ i-1 ][ j ] + T3[ i ] ) F[ i ][ min(j+F2[ i ],M) ] = F[ i-1 ][ j ] + T3[ i ]; } int Min = 0xffffff; for ( int i = 0 ; i <= M ; ++ i ) if ( Min > F[ N ][ i ] ) Min = F[ N ][ i ]; return Min; } int main() { int T,N,M; while ( cin >> T ) while ( T -- ) { cin >> N >> M; for ( int i = 1 ; i <= N ; ++ i ) cin >> T1[ i ] >> T2[ i ] >> T3[ i ] >> F1[ i ] >> F2[ i ]; cout << dp( N, M ) << endl; } return 0; }
zoj 2972 - Hurdles of 110m
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。