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

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條評論
主站蜘蛛池模板: 天天干天天干天天操 | 天天射夜夜爱 | 成人爱爱爱欧美日本视频 | 99爱国产 | 国产欧美亚洲精品第一区 | 精品欧美一区二区在线观看 | 精品国产免费一区二区 | 2023中文字幕在线观看 | 日本精品久久久一区二区三区 | 亚洲国产人久久久成人精品网站 | 97在线观看免费视频 | 久久精品国产清白在天天线 | 不卡一区二区在线 | 全部免费的毛片在线看青青 | 日韩欧美一级毛片在线 | 成人夜夜 | 中国毛片免费看 | 四虎4hu | 亚洲视频网站在线观看 | 亚洲最大激情中文字幕 | 中文字幕一区日韩在线视频 | 欧美黑人巨大3dvideo | 欧美色视频超清在线观看 | 国产99re在线观看只有精品 | 四虎在线永久视频观看 | 中文字幕av一区 | 亚洲高清视频免费 | 色老头老太做爰视频在线观看 | 天天曰曰| 成年人视频在线免费 | 另类亚洲图片 | 色综合久久久久久久久五月 | 2021久久伊人精品中文字幕有 | 国产成人禁片免费观看 | 成年人视频在线免费 | 久久久久久国产视频 | 日本xxxxx18护士xxx | 婷婷综合国产激情在线 | 国产精品无码久久综合网 | 久久aa毛片免费播放嗯啊 | 韩国欧美一级毛片免费 |