12-22 tyvj水题记录(1014)

Dec 22, 2016

“明明说好的已弃ACM了么?”

“然而看到水题根本控制不住双手T^T…正好c语言考试马上要来了, 没事刷刷水题”

tyvj是不兹词Chrome了么..登录不上, 于是手动评测(AC滑稽脸), 发现AC不了的话千万不要来找我(逃)

题目

http://www.tyvj.cn/p/1014

水题(龟速 + 龟量) ++;

这题一开始写错了, 后来改了一遍才对, PIA~

大雾实验今天做的是欲仙欲死…时间不够用了, 刷不了四题, 就刷这一题吧, 不然没时间复习别的了(J_J)

题解

1014

注释里面就是我最开始的代码, 有错误, 错误肯定是在初始化那个地方, 这里偏偏要求最小..自然而然用函数重写了一遍才写对

正常DP, 转移方程: f[i][j] = min(f[i][j], f[i][k] + f[k][j] + 三个数据相乘), 也很容易理解咯, 和Floyd一模一样

答案:

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int d[105];
int f[105][105];
//f[i][j] = min(f[i][j], f[i][k] + f[k][j] + d[i]*d[k]*d[j])

int i, j;
int g(int l, int r){
    if(!(r - l - 1)) return 0;
    if(f[l][r] < 100000000) return f[l][r];
    for(int k = l + 1; k < r; ++k)
        f[l][r] = min(f[l][r], g(l, k) + g(k, r) + d[l] * d[r] * d[k]);
    return f[l][r];
}

int main()
{
    memset(f, 127, sizeof(f));
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
        scanf("%d", &d[i]);
//    for(i = 1; i < n; ++i)
//        for(j = i + 1; j <= n; ++j)
//            for(k = i + 1; k < j; ++k){
//                if(!f[i][j]) {f[i][j] = f[i][k] + f[k][j] + d[i] * d[k] * d[j]; continue;}
//                f[i][j] = min(f[i][j], f[i][k] + f[k][j] + d[i] * d[k] * d[j]);
//            }
    printf("%d\n", g(1, n));
    return 0;
}