You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int INF = 0x3f3f3f3f ;
const int N = 110 ;
int n ; // 电桩数
int d ; // 冲一次电能跑的距离
int res = INF ;
int a [ N ] ;
/*
测试用例：
5 4
3 1 2 2 1
答案：
*/
void dfs ( int u , int r , int c ) {
if ( u = = n + 1 ) {
res = min ( res , c ) ;
return ;
}
// 现在剩余的油量是r,加满的话油量是d
// 如果现在剩余的油量r不足以跑完下一个路a[u+1],那么必须在本站加油到d
if ( d < a [ u + 1 ] ) return ;
if ( r > = a [ u + 1 ] ) { // 我有两种选择： ，
dfs ( u + 1 , r - a [ u + 1 ] , c ) ;
dfs ( u + 1 , d - a [ u + 1 ] , c + 1 ) ;
} else
dfs ( u + 1 , d - a [ u + 1 ] , c + 1 ) ;
}
int main ( ) {
cin > > n > > d ;
for ( int i = 1 ; i < = n ; i + + ) cin > > a [ i ] ;
dfs ( 0 , 0 , 0 ) ;
if ( res = = INF )
cout < < - 1 < < endl ;
else
cout < < res < < endl ;
return 0 ;
}
