济南Day3 坐标型动态规划及背包

花店橱窗布置


思路

  • $f[i][j]$表示前i个花瓶前j个花束的最大美学价值
  • $f[i][j]=max(f[i-1][k],f[i][j])$

当然还有另外一种思路(太强了!!!):

  • 整张表都是向右下方走的,向下走加上数值,向右走无影响
  • 如果向下走代表花束放入花瓶,向右走无影响代表不放入
int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数


思路

  • 因为每次取头和尾,所以一定是一个连续的区间
  • $f[i][j]$表示从i取到j的最大得分
  • $f[i][j]=max(f[i][j-1]+a[j]2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]2^(i-1+n-j+1+1))$
  • 指数是轮数,当前数前面有多少个数被取走,就有多少轮,注意一下1的问题
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×