给定一个序列,每次从前三个中选两个值并取他们的最大值累加,不足 3 个就取剩下的 1 个或 2 个的最大值累加,
求和的最小值以及取法。
每一次会取两个数,也就是会剩下一个数,所以我们可以把剩下的那个数来设状态
F[ i] [j ] 前i个数,剩余的数为j
#include <iostream> #include <cmath> #include <cstring> using namespace std; const int N =1003; struct T{ int k,i,j; }p[N][N]; int n,f[N][N],a[N]; void print(int x,int y){ if(x>1) print(x-1,p[x][y].k); if(p[x][y].i>n){printf("%d\n", p[x][y].j);return;} if(p[x][y].j>n){printf("%d\n", p[x][y].i);return;} printf("%d %d\n",p[x][y].i,p[x][y].j); } void solve(){ int i,j; memset(f,127,sizeof f); cin>>n;for(i=1;i<=n;i++) cin>>a[i]; n++; f[0][1]=0; for(i=1;i<=n/2;i++) for(j=1;j<i*2;j++){ if(f[i][j]>f[i-1][j]+max(a[i*2],a[i*2+1])) f[i][j]=f[i-1][j]+max(a[i*2],a[i*2+1]), p[i][j]=T{j,i*2,i*2+1}; if(f[i][2*i]>f[i-1][j]+max(a[i*2+1],a[j])) f[i][2*i]=f[i-1][j]+max(a[i*2+1],a[j]), p[i][2*i]=T{j,i*2+1,j}; if(f[i][2*i+1]>f[i-1][j]+max(a[i*2],a[j])) f[i][2*i+1]=f[i-1][j]+max(a[i*2],a[j]), p[i][2*i+1]=T{j,i*2,j}; } cout<<f[n/2][n]<<endl; print(n/2,n); } signed main(){ solve(); }