C 常规实现

解题思路:C语言 常规实现 
注意事项:这道题的话比较特殊，尝试从时间大的往小的逼近，dp[i]表示的是第i到结束这段时间的最大空闲时间

参考代码:

#include<stdio.h>

#include<stdlib.h>

int max( int a , int b ) {

if( a < b ) a = b ; 

return a ; 

}

int main (  ) {

int n , i , j , s ;  

int dp[10001] = {0} , b[10001] = {0} , t[10001] = {0} , biao[10001] = {0} ; 

scanf( "%d %d" , &s , &n ) ; 

for( i = 1 ; i <= n ; i++ ) {

scanf( "%d %d" , &b[i] , &t[i] ) ; 

biao[b[i]]++ ; 

}

dp[s+1] = 0 ; 

for( i = s ; i >= 1 ; i-- ) {

if( biao[i] == 0 ) {

dp[i] = dp[i+1] + 1 ; 

}

else {

for( j = 1 ; j <= n ; j++ ) {

if( i == b[j] ) {

dp[i] = max( dp[i+t[j]] , dp[i] ) ; 

}

}

}

}

printf( "%d" , dp[1] ) ; 

return 0 ; 

}