网络培训网站开发文献综述,微网站 网页,南宁seo推广,wordpress 商店模板正题
链接 需要纪中OJ账号 有n个数#xff0c;可以选择删除一段区间#xff0c;价值为|xi – xk|*(k-i1)。求删完所有数的最大价值 输入输出#xff08;需要自取#xff09; Input 输入文件的第一行为一个正整数N#xff0c;第二行有N个用空格隔开的N个不同的正整…正题
链接 需要纪中OJ账号 有n个数可以选择删除一段区间价值为|xi – xk|*(k-i1)。求删完所有数的最大价值 输入输出需要自取 Input 输入文件的第一行为一个正整数N第二行有N个用空格隔开的N个不同的正整数。 Output 输出文件包含一个正整数为操作的最大值 Sample Input 6 54 29 196 21 133 118 Sample Output 768 解题思路
删除一个区间就很快想到这就是区间dp然后就使用了曾经石子合并问题的做法。 代码
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n,a[101],f[101][101];
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]);for (int i1;in;i)for (int ji;jn;j){if (ij) f[i][j]a[i];else f[i][j]abs(a[i]-a[j])*(j-i1);//初始化为所有区间直接删}for (int k2;kn;k)//多个多个合并{for (int i1;in;i){int jik;if (jn)for (int di;dj;d)f[i][j]max(f[i][j],f[i][d]f[d1][j]);//看看分开删还是一起删价值更大}}printf(%d,f[1][n]);//删除1到N的数
}
