xml地图|网站地图|网站标签 [设为首页] [加入收藏]

伟大航路的延续 海贼王新电影12月15日上映 澳门新葡新京官方网站

由尾田荣一郎原作的日本国民级大人气漫画《海贼王》,其第12部剧场版动画《海贼王 FILM Z》,预计将于今年12月15日于日本全国上映。原作者尾田荣一郎将担任该剧场动画的综合制片人;而脚本,则由曾经为《SMAP×SMAP》、《矛X盾》等多部大人气综合节目担任系列构成的知名放送作家铃木修(铃木おさむ)担任,铃木修先生也是《海贼王》系列的大粉丝。关于本次为《海贼王》剧场动画担任脚本,他也做出了“身为《海贼王》的忠实粉丝,能够让我做鱼人岛篇后面的内容感到非常高兴。新世界突入篇的内容做成电影一定令人热血沸腾,大家敬请期待吧”这样的发言。  本次铃木修先生的起用,是富士电台的种田义彦制作人大力推荐的结果。种田制作人说,“首先,铃木修先生是《海贼王》系列的忠实粉丝,另外,作为多部综合节目的放送作家,铃木修先生非常的有人气,也是目前日本的粉丝最期待其担任脚本的人选。由他来担任作品的脚本,也能以粉丝代表的身份,与尾田综合制作人商量切磋,相信能制作出让人热血沸腾激动不已的好电影。”由此,铃木X尾田的强强组合也终于实现了。  《海贼王》是尾田荣一郎于1997年开始在集英社杂志《周刊少年JUMP》上连载的超人气王道类少年漫画,描绘了以“传说中的大秘宝ONE PIECE”为目标,主人公MONKEY.D.路飞和他的伙伴们一路以来进行的种种冒险与热血友情的物语。连载15年来,累积发行数超过了2亿6000万部。目前,其连载15周年纪念的展览会“海贼王展~原画×映像×体感的ONE PIECE”正在东京六本木的MORI ARTS CENTER GALLERY展开。  此外,《海贼王 FILM Z》的主题曲也将由曾制作过《Perfume》等歌曲的音乐制作人中田ヤスタカ担任。中田也是为目前举办中的“海贼王15周年展”上担任主题曲的制作。剧场动画的监督由人气动画《光之美少女》系列的监督长峯达也担任,这也是他初次挑战《海贼王》的剧场动画;作画则由《海贼王》剧场动画第10作《ONE PIECE FILM STRONG WORLD》的作画佐藤雅将继续担任。  《海贼王 FILM Z》的特报第1弹,预定将于本月21日开始在日本全国剧场上映,届时粉丝们将看到尾田荣一郎一直使用的工作台,此外还有剧场版中登场的新角色“Z”的设定画,感兴趣的粉丝不妨多加关注一下。《海贼王 FILM Z》制作阵容:监督:长峯达也综合制片人:尾田荣一郎脚本:铃木修作画:佐藤雅将主题曲:中田ヤスタカ

题目概述

POJ 4979 海贼王的伟大航路

输入
输入数据包含多行。
第一行包含一个整数N(2 < N ≤ 16),代表伟大航路上一共有N个岛屿(包含起点的罗格镇和终点的拉夫德鲁)。其中,起点的编号为1,终点的编号为N。
之后的N行每一行包含N个整数,其中,第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个岛屿出发到第j个岛屿需要的时间t(0 < t < 10000)。第i行第i个整数为0。

输出
输出为一个整数,代表路飞一行从起点遍历所有中间岛屿(不重复)之后到达终点所需要的最少的时间。

样例输入
5
0 18 13 98 8
89 0 45 78 43
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0

样例输出
137

提示
对于样例输入:可能的路径及总时间为:
1,2,3,4,5: 18+45+96+52=211
1,2,4,3,5: 18+78+29+12=137
1,3,2,4,5: 13+38+78+52=181
1,3,4,2,5: 13+96+19+43=171
1,4,2,3,5: 98+19+45+12=174
1,4,3,2,5: 98+29+38+43=208
所以最短的时间花费为137
单纯的枚举在N=16时需要14!次运算,一定会超时。

澳门新葡新京官方网站 1

DP算法分析

这道题感觉上像是DP,但是我总也想不出个具体的转移方程。
以下摘录网上别人的代码和想法。
内存2576kb,时间24ms。

  • 受到限制的有集合中元素,和最后到达的地点,与之前的顺序无关,最后从1到n也与2到n-1的顺序无关
  • 考虑状态压缩,先处理1到n-1结点,最后处理中间部分结点到n结点 d[S][i]=min(d[S][i],d[S-(1<< i)][j]+dist[j][i]);
#include<cstdio>
#include<climits>
#include<iostream>
using namespace std;
#define N 17
int d[1<<N][N],dist[N][N];
int n,i,j,S,ans;bool f;
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&dist[i][j]);
    n-=2;
    for(int i=0;i<n;i++)    d[(1<<i)][i]=dist[0][i+1];

    for(S=0;S<(1<<n);S++){
        for(i=0;i<n;i++) if(S==(1<<i)) f=true;
        if(f) {f=false;continue;
    }
        for(i=0;i<n;i++) d[S][i]=INT_MAX/2;
        for(i=0;i<n;i++){
            if(S&(1<<i)){
                for(int j=0;j<n;j++){
                    if(i==j) continue;
                    if(S&(1<<j))
                        d[S][i]=min(d[S][i],d[S-(1<<i)][j]+dist[j+1][i+1]);
                }
            }
        }
    }
    ans=INT_MAX,S=(1<<n)-1;
    for(int i=0;i<n;i++) ans=min(ans,d[S][i]+dist[i+1][n+1]);
    printf("%d",ans);
    return 0;
}

DFS算法分析

实际上,在作业中老师把他归到搜索的题目,所以我就想到了用DFS。然而我的代码比较拙劣,TLE了。
又搜索相关剪枝策略,贴上别人的代码。关键的部分在于以下这个nposition数组记录了[1~po][选择方式]的最优解,可以减除大量无关解。
内存2088kb,时间76ms。

#include<cstdio>
#include<string.h>
#include<stdlib.h>
#include<math.h>
const int inf = 0x3f3f3f3f;
int step;
int minstep;
int a[16][16];
int book[15];
int postion[20];
int n;
int npostion[15][1<<15];
int po;
void dfs(int cur,int qc)
{
    if(cur+2==n)
    {
        step+=a[qc][n-1];
        if(step<minstep)
            minstep=step;
        step-=a[qc][n-1];
        return;
    }
    for(int i=1; i<n-1; i++)
    {
        if(!book[i])// has been through
        {
            if(step>=minstep)
                continue;
            if((npostion[i][po+postion[i-1]]<=step+a[qc][i]))
                continue; //重要剪枝语句,我把这一句写在for前面便导致超时了
            po+=postion[i-1];
            step+=a[qc][i];
            npostion[i][po]=step;
            book[i]=1;
            dfs(cur+1,i);
            po-=postion[i-1];
            book[i]=0;
            step-=a[qc][i];
        }
    }
}
int main()
{
    for(int i=0; i<14; i++)
        postion[i]=1<<i;
    while (~scanf("%d",&n))
    {
        po=0;
        step=0;
        minstep=1e17;
        memset(npostion,inf,sizeof(npostion));
        memset(a,0,sizeof(a));
        memset(book,0,sizeof(book));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&a[i][j]);
        dfs(0,0);
        printf("%dn",minstep);
    }
    return 0;
}

本文由澳门新葡亰是真的吗发布于运营路线,转载请注明出处:伟大航路的延续 海贼王新电影12月15日上映 澳门新葡新京官方网站

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。