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; }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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