亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

1552. Brainfuck

系統 2033 0

http://acm.timus.ru/problem.aspx?space=1&num=1552

“You may assume that optimal program will not have to modify more than four memory cells.”

剛開始沒有注意到這句話 一直想不到怎么解。后來才發現

直觀的解法就是 dp[50][27][27][27][27][4] 可以用滾動數組優化內存 但是記錄路徑的部分沒有優化 會超內存

后來看了大牛的提示原來只需要用 dp[50][27][27][27][4] 降低了一個維度??

應為當 dp[i][l][r][k][u][w] 中的 i 和 w 確定了以后 其中 l,r,k,u 中的某一個就確定了大小,而且所在原來多維數組的位置也確定了

比如說 dp[i][l][r][k][1] 所代表的就是原來的 dp[i][l][x][r][k][1]??x 大小也可以根據 所表示的第 i 個字符來確定

所以可以少一個維度

然后需要的就是細心了 有點繁瑣

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<string>

#include<queue>

#include<stack>

#include <iomanip>

using namespace std;

#define LL long long

const double eps=1e-6;

const int INF=0x3f3f3f3f;

const int N=51;

const int M=27;

int sum[2][M][M][M][4];

struct node

{

    int l,r,k;

    int w;

}path[N][M][M][M][4];

string s;

vector<char>road;

int Fstep(int i,vector<int>&a,int w,vector<int>&b,int e)

{

    int tmp=abs(w-e);

    a.insert(a.begin()+w,s[i-1]-'a'+1);

    b.insert(b.begin()+e,s[i]-'a'+1);

    for(int j=0;j<4;++j)

    {

        if(j==e) tmp+=((a[j]==0)?s[i]:abs(b[j]-a[j]));

        else b[j]=a[j];

    }

    a.erase(a.begin()+w);

    b.erase(b.begin()+e);

    return tmp;

}

void add1(int i,vector<int> a,int w,vector<int> b,int e)

{

    int m; char c;

    if(i-2>=0)

    a.insert(a.begin()+w,s[i-2]-'a'+1);

    else

    a.insert(a.begin()+w,0);

    b.insert(b.begin()+e,s[i-1]-'a'+1);

    if(b[e]>a[e]) c='+';

    else c='-';

    m=((a[e]==0)?s[i-1]:abs(a[e]-b[e]));

    while(m--) road.push_back(c);

}

void add(int i,vector<int>&b,int &e)

{

    int m=0;char c;

    road.push_back('.');

    vector<int>a;

    a.push_back(path[i][b[0]][b[1]][b[2]][e].l);

    a.push_back(path[i][b[0]][b[1]][b[2]][e].r);

    a.push_back(path[i][b[0]][b[1]][b[2]][e].k);

    int w=path[i][b[0]][b[1]][b[2]][e].w;

    if(e>w) c='>';

    else c='<';

    if(i>1)

    m=abs(e-w);

    add1(i,a,w,b,e);

    b=a;e=w;

    while(m--) road.push_back(c);

}

int main()

{

    //freopen("data.in","r",stdin);

    while(cin>>s)

    {

        vector<int>a,b;

        int n=s.length();

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

        memset(path,0,sizeof(path));

        for(int w=0;w<4;++w)

        sum[1][0][0][0][w]=(int(s[0]));

        a.push_back(0);a.push_back(0);a.push_back(0);

        b.push_back(0);b.push_back(0);b.push_back(0);

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

        {

            for(a[0]=0;a[0]<=26;++a[0])

            for(a[1]=0;a[1]<=26;++a[1])

            for(a[2]=0;a[2]<=26;++a[2])

            for(int w=0;w<4;++w)

            sum[(i+1)%2][a[0]][a[1]][a[2]][w]=-1;

            for(a[0]=0;a[0]<=26;++a[0])

            for(a[1]=0;a[1]<=26;++a[1])

            for(a[2]=0;a[2]<=26;++a[2])

            for(int w=0;w<4;++w)

            if(sum[i%2][a[0]][a[1]][a[2]][w]!=-1)

            {

                for(int e=0;e<4;++e)

                {

                    int tmp=Fstep(i,a,w,b,e);

                    if(sum[(i+1)%2][b[0]][b[1]][b[2]][e]==-1||sum[(i+1)%2][b[0]][b[1]][b[2]][e]>sum[i%2][a[0]][a[1]][a[2]][w]+tmp)

                    {

                        sum[(i+1)%2][b[0]][b[1]][b[2]][e]=sum[i%2][a[0]][a[1]][a[2]][w]+tmp;

                        path[i+1][b[0]][b[1]][b[2]][e].l=a[0];

                        path[i+1][b[0]][b[1]][b[2]][e].r=a[1];

                        path[i+1][b[0]][b[1]][b[2]][e].k=a[2];

                        path[i+1][b[0]][b[1]][b[2]][e].w=w;

                    }

                }

            }

        }

        int W,MIN=INF;

        for(int l=0;l<=26;++l)

        for(int r=0;r<=26;++r)

        for(int k=0;k<=26;++k)

        for(int w=0;w<4;++w)

        if(sum[n%2][l][r][k][w]!=-1&&sum[n%2][l][r][k][w]<MIN)

        {

            MIN=sum[n%2][l][r][k][w];

            a[0]=l;a[1]=r;a[2]=k;

            W=w;

        }

        road.clear();

        for(int i=n;i>0;--i)

        add(i,a,W);

        for(int i=road.size()-1;i>=0;--i)

        cout<<road[i];

        cout<<endl;

    }

    return 0;

}


    

?

1552. Brainfuck


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 四虎国产在线观看 | 伊在人亚洲香蕉精品播放 | 激情五月婷婷红人馆 | 九九影院在线观看 | 九天玄帝诀在线观看 | 国产精品全国探花泡良大师 | 国产精品久久久一区二区三区 | 欧美.成人.综合在线 | 一区 在线播放 | 国产午夜成人无码免费看 | 九九热国产精品视频 | 国产成人综合久久精品亚洲 | 亚洲成人黄色在线 | 亚洲精品福利视频 | 伊人久久网站 | 婷婷综合在线观看丁香 | 伊人中文字幕在线 | 狠狠色丁香久久婷婷综合丁香 | 老子影院午夜精品欧美视频 | 免费在线看h | 欧美日韩亚毛片免费观看 | 一级毛片不卡免费看老司机 | 中文字幕久热精品视频免费 | 国产偷国产偷在线高清 | 清纯唯美亚洲综合日韩第 | 欧美成年黄网站色高清视频 | 国产欧美精品专区一区二区 | 日本黄色免费一级片 | 久久精品资源站 | 黄色男人的天堂 | 亚洲精品乱码中文字幕无线 | 成年女人毛片免费播放视频m | 99久久99热久久精品免费 | 日本成片 | 日本一区二区成人教育 | 久一视频在线 | 日日私人影院 | 99re6这里只有精品视频 | 国产99久久久久久免费看 | 99视频全部免费 | 日本在线亚洲 |