cf D. Levko and Array

http://codeforces.com/contest/361/problem/D
隣接する2つの数の差の絶対値を二分で探索し,その後dpで数の変化回数を記録した.dp[i]は、iより前に変化した回数を表し、|a[i]−a[j]|<=(i−j)*midが変化する必要がある場合を表す.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #define LL __int64

 5 using namespace std;

 6 const LL inf=2000000000;

 7 int dp[20000];

 8 int n,k;

 9 LL a[20000];

10 LL ABS(LL a)

11 {

12     if(a<0) return -a;

13     return a;

14 }

15 bool ok(LL c)

16 {

17     memset(dp,0,sizeof(dp));

18     for(int i=1; i<=n; i++)

19     {

20         dp[i]=i;

21         for(int j=1; j<i; j++)

22         {

23             if(ABS(a[i]-a[j])<=(LL)(i-j)*c)

24                dp[i]=min(dp[i],dp[j]+(i-j-1));

25         }

26         if(dp[i]+(n-i-1)<=k) return true;

27     }

28     return false;

29 }

30 

31 int main()

32 {

33     while(scanf("%d%d",&n,&k)!=EOF)

34     {

35         for(int i=1; i<=n; i++)

36         {

37             scanf("%I64d",&a[i]);

38         }

39         LL l=0,r=inf;

40         while(l<=r)

41         {

42             LL mid=(l+r)/2;

43             if(ok(mid))

44             {

45                 r=mid-1;

46             }

47             else l=mid+1;

48         }

49         printf("%I64d
",l);

50     }

51     return 0;

52 }

View Code