记忆化搜索 – Elijahqi-Blog

STL

bzoj 3679 数字之积

Description 一个数x各个数位上的数之积记为f(x) <不含前导零> 求[L, 阅读更多…

由elijahqi，2年前

hash

bzoj5248[2018多省省队联测]一双木棋

Description 菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。棋局开阅读更多…

由elijahqi，2年前

动态规划

bzoj1048 [HAOI2007]分割矩阵

Description 　　将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，阅读更多…

由elijahqi，2年前

动态规划

codeforces 678E Another Sith Tournament

The rules of Sith Tournament are well known to eve 阅读更多…

由elijahqi，3年前

树形dp

皇宫看守

题目背景太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。题目描述皇宫以午门为起点，直到后宫阅读更多…

由elijahqi，3年3年前

图的联通

bzoj1589&luogu2921 [USACO08DEC]Trick or Treat on the Farm

题目描述 Every year in Wisconsin the cows celebrate th 阅读更多…

由elijahqi，3年前

动态规划

noip2016 愤怒的小鸟 luogu 2831

题目描述 Kiana最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有阅读更多…

由elijahqi，3年3年前

动态规划

luogu 1049 装箱问题

题目描述有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个阅读更多…

由elijahqi，3年前

记忆化搜索

luogu1002 过河卒

题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C 阅读更多…

由elijahqi，3年前

记忆化搜索

noip2006 能量项链

#include<cstdio>
#include<cstring>
int n,a[220],max,data[220][220];
void f(int i,int j){
    if(i==j){
        data[i][j]=0;
        return;
    }
    int maxx=0,tmp=0;
    for (int k=i;k<=j-1;++k){
        if (data[i][k]==-1) f(i,k);
        if (data[k+1][j]==-1) f(k+1,j);
        tmp=data[i][k]+data[k+1][j]+a[i]*a[k+1]*a[j+1];
        if (tmp>maxx) maxx=tmp;
    }
    data[i][j]=maxx;
}
int main(){
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=n+1;i<=2*n;++i) a[i]=a[i-n];
    for (int i=1;i<=n;++i){
        memset(data,-1,sizeof(data));
        f(i,i+n-1);
        if (max<data[i][i+n-1]) max= data[i][i+n-1];
    } 
    printf("%d",max);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

#include<cstdio>

#include<cstring>

int n,a[220],max,data[220][220];

void f(int i,int j){

if(i==j){

data[i][j]=0;

return;

}

int maxx=0,tmp=0;

for (int k=i;k<=j-1;++k){

if (data[i][k]==-1) f(i,k);

if (data[k+1][j]==-1) f(k+1,j);

tmp=data[i][k]+data[k+1][j]+a[i]*a[k+1]*a[j+1];

if (tmp>maxx) maxx=tmp;

}

data[i][j]=maxx;

}

int main(){

freopen("energy.in","r",stdin);

freopen("energy.out","w",stdout);

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d",&a[i]);

for(int i=n+1;i<=2*n;++i) a[i]=a[i-n];

for (int i=1;i<=n;++i){

memset(data,-1,sizeof(data));

f(i,i+n-1);

if (max<data[i][i+n-1]) max= data[i][i+n-1];

}

printf("%d",max);

return 0;

}

由elijahqi，3年前