题目传送门
解题思路:
f[i][j]表示当前在第i个时间用了j此移动了,a[i][j]表示第i个时间j号树的苹果下落数.
如果移动了单数次,则在2号树,否则在1号树.
对于每个状态,我可以在上一个时间从另一棵树过来,也可以是我没动.
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 int t,n,f[1001][31],a[1001][2],ans; 7 8 inline int max(int s,int d) { 9 if(s >= d) return s; 10 return d; 11 } 12 13 int main() { 14 scanf("%d%d",&n,&t); 15 for(int i = 1;i <= n; i++) { 16 int u; 17 scanf("%d",&u); 18 a[i][u-1] = 1; 19 } 20 for(int i = 1;i <= n; i++) 21 for(int j = 0;j <= min(i,t); j++) 22 if(j % 2 == 1) 23 f[i][j] = max(f[i-1][j],f[i-1][j-1]) + a[i][1]; 24 else 25 f[i][j] = max(f[i-1][j],f[i-1][j-1]) + a[i][0]; 26 for(int i = 0;i <= t; i++) 27 ans = max(ans,f[n][i]); 28 printf("%d",ans); 29 return 0; 30 }
然后,我发现可以压一维.
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 int t,n,f[31],a[1001][2],ans; 7 8 inline int max(int s,int d) { 9 if(s >= d) return s; 10 return d; 11 } 12 13 int main() { 14 scanf("%d%d",&n,&t); 15 for(int i = 1;i <= n; i++) { 16 int u; 17 scanf("%d",&u); 18 a[i][u-1] = 1; 19 } 20 for(int i = 1;i <= n; i++) 21 for(int j = 0;j <= min(i,t); j++) 22 if(j % 2 == 1)//在2号树 23 f[j] = max(f[j],f[j-1]) + a[i][1]; 24 else//在一号树 25 f[j] = max(f[j],f[j-1]) + a[i][0]; 26 for(int i = 0;i <= t; i++) 27 ans = max(ans,f[i]); 28 printf("%d",ans); 29 return 0; 30 }