Submission #1531139

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int maxn = (int)2*1e5+10;
const int size = 26;
const int inf = (int)1e9+7;

int dp[maxn], vis[maxn];
int nxt[maxn][size];
char A[maxn];
int n;

//////////////辅助函数/////////////
int id(char c) { return c-'a'; }

int f(int x) {
  if (x > n) return 0;
  int &ans = dp[x];
  if (vis[x]) return ans;
  vis[x] = 1; ans = inf;
  for (int i=0; i<size; i++) {
    ans=min(ans, f(nxt[x][i]+1)+1);
    //if (x == 0) printf("%c %d\n", 'a'+i, ans);
  }
  return ans;
}

void print_ans(int x) {
  if (x > n) return ;
  for (int i=0; i<size; i++) 
    if (dp[x]==dp[nxt[x][i]+1]+1) {
      putchar(i+'a');
      print_ans(nxt[x][i]+1);
      break;
    }
}

//////////////主要函数/////////////
void init() {
  scanf("%s", A);
  n = strlen(A);
  for (int i=0; i<size; i++)
    nxt[n][i] = n;
  for (int i=n-1; i>=0; i--) 
    for (int j=0; j<size; j++) {
      if (id(A[i]) == j) nxt[i][j] = i;
      else nxt[i][j] = nxt[i+1][j];
    }
}

void solve() {
  f(0);
  //for (int i=0; i<n; i++) printf("%d ", dp[i]); 
  //printf("\n");
  print_ans(0);
  putchar('\n');
}

int main() {
  init();
  solve();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:40:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", A);
                 ^

Judge Result