首页 > 代码库 > 爱奇艺全国高校算法大赛初赛C
爱奇艺全国高校算法大赛初赛C
区间$dp$。
倒着考虑这件事件，肯定有最后一个取走的数字，假设是$a[k]$，那么最后一次取走的价值肯定是$a[0]*a[k]*a[n+1]$，之前取走的价值和为$[1,k-1]$的价值加上$[k+1,n]$的价值。
设$dp[L][R]$表示取完区间$[L,R]$的最大价值，$dp[L][R] = a[L-1]*a[k]*a[R+1] + dp[L][k-1] + dp[k+1][R]$，枚举$k$取最大值。
#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;long long a[600];long long dp[600][600];int n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } a[0] = 1; a[n+1] = 1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int L = j; int R = L+i-1; if(R>n) continue; for(int k = L;k<=R;k++) { dp[L][R] = max(dp[L][R],dp[L][k-1]+dp[k+1][R]+a[k]*a[L-1]*a[R+1]); } } } printf("%lld\n",dp[1][n]); return 0;}爱奇艺全国高校算法大赛初赛C
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。