- 凯撒密码
- 2017-07-16 17:05:35 @
为什么只能过7个点?
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#define INF (0x3f3f3f3f)
using namespace std;
int wdlen;
char wd[70010];
int dp[70010];
int sec[70010];
int square(int tm) {return tm*tm;}
int main () {
ios::sync_with_stdio(false);
cin.getline(&wd[1],INF);
wdlen=strlen(&wd[1]);
memset(dp,INF,sizeof(dp));
dp[0]=0;
sec[0]=INF;
for(int i=1;i<=wdlen;i++) {
for(int j=1;square(j)<=i;j++)
if (dp[i-square(j)]+1<dp[i]&&sec[i-square(j)]>=j) {
dp[i]=dp[i-square(j)]+1;
sec[i]=j;
}
}
stack<char> st;
int now=wdlen;
while(now>0) {
for(int i=now;i>now-sec[now];i--)
for(int j=i;j>now-square(sec[now]);j-=sec[now])
st.push(wd[j]);
now-=square(sec[now]);
}
while(!st.empty()) cout<<st.top(),st.pop();
return 0;
}
0 条评论
目前还没有评论...