P1156 垃圾陷阱
思路
用 f [ i ] [ j ] 来表示第 i 个垃圾被扔下时垃圾堆的高度为 j 时能活下去的时间。
一开始考虑在 j 枚举时间，结果T掉了一个点，反而在高度为１～１００的情况下枚举高度更方便。
给时间先排序 ( 数据里给出的并不是升序的时间线 ) , 就能保证如果牛能活 ( 注意牛有濒死状态, 也就是 0 血的时候还能秀) 到扔下第 i + 1 个垃圾时, 如果垃圾高度够了此时耗费的时间是最优的.
如果不行的话就让牛一直吃, 找到他最多能活到什么时候.
CODE
#include < bits/stdc++.h >
#define dbg( x ) cout << #x << " = " << x << endl
#define eps 1 e - 8
#define pi acos( - 1.0 )
using namespace std ;
typedef long long LL ;
const int inf = 0x 3f3f3f3f ;
template < class T > inline void read(T & res )
{
char c ;T flag = 1 ;
while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}
namespace _buff {
const size_t BUFF = 1 << 19 ;
char ibuf [BUFF ], *ib = ibuf , *ie = ibuf ;
char getc() {
if (ib == ie ) {
ib = ibuf ;
ie = ibuf + fread(ibuf , 1 , BUFF , stdin );
}
return ib == ie ? - 1 : *ib ++ ;
}
}
int qread() {
using namespace _buff ;
int ret = 0 ;
bool pos = true ;
char c = getc();
for (; (c < ' 0 ' || c > ' 9 ' ) && c != ' - ' ; c = getc()) {
assert( ~c );
}
if (c == ' - ' ) {
pos = false ;
c = getc();
}
for (; c >= ' 0 ' && c <= ' 9 ' ; c = getc()) {
ret = (ret << 3 ) + (ret << 1 ) + (c ^ 48 );
}
return pos ? ret : -ret ;
}
const int maxn = 1007 ;
int d , g ;
struct node {
int t , f , h ;
} a [maxn ];
int f [maxn ][maxn ];
bool cmp(node a , node b ) {
return a . t < b . t ;
}
int main()
{
read(d );read(g );
for ( int i = 1 ; i <= g ; ++i ) {
read( a [i ]. t );
read( a [i ]. f );
read( a [i ]. h );
}
sort(a + 1 , a + g + 1 , cmp );
f [ 0 ][ 0 ] = 10 ;
a [ 0 ] = { 0 , 0 , 0 };
for ( int i = 0 ; i < g ; ++i ) {
for ( int j = 0 ; j <= d ; ++j ) {
if( f [i ][j ] >= a [i + 1 ]. t ) {
int new_high = j + a [i + 1 ]. h ;
if(new_high >= d ) {
printf( " %d \n " , a [i + 1 ]. t );
return 0 ;
}
f [i + 1 ][j ] = max( f [i + 1 ][j ], f [i ][j ] + a [i + 1 ]. f );
f [i + 1 ][new_high ] = max( f [i + 1 ][new_high ], f [i ][j ]);
}
}
}
int ans = INT_MIN ;
for ( int i = 1 ; i <= g ; ++i ) {
ans = max(ans , f [i ][ 0 ]);
}
cout << ans << endl ;
return 0 ;
}
投递中国石化等公司10个岗位 >
