bzoj3594 [Scoi2014]方伯伯的玉米田

二维树状数组优化DP

DP状态很容易想到：dp[i][j]表示到第i颗玉米，用了j次提升，最多保留多少：

转移：

　　　　dp[i][j]=dp[k][j]+1(k<=i&&a[k]<=a[i)

　　　　dp[i][j]=dp[k][j+a[i]-a[k]]+1 (j<=i&&a[k]<=a[i])

这两种转移都可以用二维树状数组优化：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<string>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<set>
13 #define lowbit(x) x&-x
14 using namespace std;
15 int c[6060][555],hh[10010][555],a[10010],n,m,ans,Max; 
16 int getint()
17 {
18     int ret=0,f=1;
19     char ch=getchar();
20     while(ch<'0'||ch>'9')
21     {
22         if(ch=='-')f=0;
23         ch=getchar();
24     }
25     while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();
26     return f==1?ret:-ret;
27 }
28 void add(int a,int b,int x)
29 {
30     for(int i=a;i<=Max+m;i+=lowbit(i))
31         for(int j=b;j<=m+1;j+=lowbit(j))
32             c[i][j]=max(c[i][j],x);
33 }
34 int query(int a,int b)
35 {
36     int ret=0;
37     for(int i=a;i;i-=lowbit(i))
38         for(int j=b;j;j-=lowbit(j))
39             ret=max(c[i][j],ret);
40     return ret;
41 }
42 int main()
43 {
44     n=getint(),m=getint();
45     for(int i=1;i<=n;i++)
46     {
47         a[i]=getint();
48         Max=max(Max,a[i]);
49     }
50     for(int i=1;i<=n;i++)
51         for(int j=m;j>=0;j--)
52         {
53             hh[i][j]=query(a[i]+j,j+1)+1;
54             ans=max(ans,hh[i][j]);
55             add(a[i]+j,j+1,hh[i][j]);
56         }
57     printf("%d
",ans);
58     return 0;
59 }