跳至正文

能量项链 解题报告

  • OI路程

额,花了我三四个小时的时间,终于知道了,是动态规划的题目(我以前做过,不过那个时候真是不知不觉过去的。),我以前只做过背包的题目,这个题目是这暑假以来觉得最复杂的题目了,因为非动态规划的代码一看就能看懂,动态规划的,方程没想通你就看不懂代码!
我的方程是:f[i][j] = max(f[i][k – i] + f[k][j – k + i] + boll[i] boll[i + j] boll[k])); 其中f[i][j]的意思是从i开始j个珠子的最大能量数,boll[i]是下标为i的珠子的能量。然后就是要注意一下细节,有人的实现方法是使用了长度为200的数组,有人是使用了mod;在这里我是用的后者,用了mod,牺牲了效率,节省了空间。
这题确实要做下纪念,我的算法水平从今天开始会向新的高度上升,我会站在世界的顶点的!

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
unsigned f[100][101];
int boll[100];
int n;

int main(void)
{
 int i, j, k;
 unsigned max = 0;
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 scanf(%d, &boll[i]);
 }

 for(j = 2; j <= n; j++){
 for(i = 0; i < n; i++){
 for(k = i + 1; k < i + j; k++){
 f[i][j] = max(f[i][j], f[i][k - i] +
 f[k % n][j - k + i] +
 boll[i] * boll[(i + j) % n] *
 boll[k % n]);
 }
 }
 }

 for(i = 0; i < n; i++){
 if(max < f[i][n]){
 max = f[i][n];
 }
 }

 printf(%u\\n, max);
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。