求助UVA水题
查看原帖
求助UVA水题
270006
Trafford1894楼主2020/9/11 21:58

RT,样例过了,求大佬Debug



#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;

string _myStr;
int _startIndex;
int _endIndex;
string _ans;
int _ians;
int _maxLen = -1;
int _num;
bool _dp[1009][1009];

string CalcStr (int fir, int lst) {
  string res = "";

  for (int i = fir; i < lst + 1; i++) {
    res += _myStr[i];
  }

  return res;
}

void Init () {
  for (int i = 0; i < _myStr.length(); i++) {
    _dp[i][i] = true;//the i'th char on the string MUST be a padlindrone
  }
}

void ParseIn () {
  memset(_dp, false, sizeof(_dp));

  ifstream inFile ("padlinSubDp.in");

  getline(cin, _myStr);

  inFile.close();

  Init();
}

void Core () {
  _maxLen = -1;

  //from top to bottom, or i + 1 must not be true
  for (int i = _myStr.length() - 1; i > -1; i--) {
    for (int m = i + 1; m < _myStr.length(); m++) {
      if (_myStr[i] != _myStr[m]) {
	//cout << i << " " << m << endl;
	_dp[i][m] = false;//if the tail and the head don't equal, it must not be a padlindrone
	continue;
      }

      if (i + 1 > m - 1) {
	_dp[i][m] = true;//if there is nothing left for the string, it must be true
	continue;
      }

      _dp[i][m] = _dp[i + 1][m - 1];//cut of the head and the tail, it comes from the string: i + 1, m - 1
      //cout << i << " " << m << endl;
      //cout << _dp[i][m] << endl;
    }
  }

  //cout << _dp[1][4] << endl;

  for (int i = 0; i < _myStr.length(); i++) {
    for (int m = 0; m < _myStr.length(); m++) {
      if (_dp[i][m]) {
	//cout << i << " " << m << endl;
	if (m - i > _maxLen) {
      //cout << m - i << endl;
	  _maxLen = m - i;
	  _startIndex = i;
	  _endIndex = m;
	}
      }
    }
  }

  _ans = CalcStr(_startIndex, _endIndex);
  //cout << _startIndex << " " << _endIndex << endl;
  _ians = _endIndex - _startIndex + 1;
}

void CWriteOut () {
  //for (int i = 0; i < _myStr.length(); i++) {
  //for (int m = 0; m < _myStr.length(); m++) {
  //cout << _dp[i][m] << " ";
  //}

  //cout << endl;
  //}

  cout << _ians << endl;
  //getchar();
}

int main () {
  cin >> _num;
  getline(cin, _myStr);

  for (int i = 1; i < _num + 1; i++) {
    ParseIn();
    //cout<<_myStr<<endl;
    Core();
    CWriteOut();
  }

  return 0;
}
2020/9/11 21:58
加载中...