7个点,大牛求救。

为什么只能过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 条评论

目前还没有评论...

信息

ID
1480
难度
7
分类
字符串 | 动态规划 | 背包 点击显示
标签
递交数
800
已通过
138
通过率
17%
被复制
3
上传者