待考察 USACO07JAN Problem Solving

发表于 | 分类于 |
字数统计: 256 字

题目地址

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,b,f[605][305],A[305],B[305],sum[305],sumb[305],ans;
void init(){
    b=read(),n=read();
    for(int i=1;i<=n;i++)
        A[i]=read(),B[i]=read(),sum[i]=sum[i-1]+A[i],sumb[i]=sumb[i-1]+B[i];
}
void solve(){ 
    f[2][0]=b;
    for(int i=1;i<=n;i++)
        if(b>=sum[i]&&b>=sumb[i])f[2][i]=b-sumb[i];
        else f[2][i]=-INF;
    for(int i=3;i<=2*n;i++){
        f[i][0]=b;	
        for(int j=1;j<=n;j++){
            f[i][j]=-INF;
            for(int k=0;k<=j;k++)
                if(f[i-1][k]-(sum[j]-sum[k])>=0)
                    f[i][j]=max(f[i][j],b-(sumb[j]-sumb[k]));
        }
        if(f[i][n]>=0){
            ans=i;break;
        }
    }
    printf("%d\n",ans+1);
}
int main(){
    init();
    solve();
    return 0;
}