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.”
剛開始沒有注意到這句話 一直想不到怎么解。后來才發(fā)現(xiàn)
直觀的解法就是 dp[50][27][27][27][27][4] 可以用滾動數(shù)組優(yōu)化內(nèi)存 但是記錄路徑的部分沒有優(yōu)化 會超內(nèi)存
后來看了大牛的提示原來只需要用 dp[50][27][27][27][4] 降低了一個維度??
應為當 dp[i][l][r][k][u][w] 中的 i 和 w 確定了以后 其中 l,r,k,u 中的某一個就確定了大小，而且所在原來多維數(shù)組的位置也確定了
比如說 dp[i][l][r][k][1] 所代表的就是原來的 dp[i][l][x][r][k][1]??x 大小也可以根據(jù) 所表示的第 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;
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
