【mxqz】这题有没有 $O(n \times k)$ 的 dp 做法？

我的想法是维护一个

bk[i][j]

数组，表示前

i

个数字划分

j

段的乘积值最大的情况下的最后一个数字（例如

12 \times 345

，

bk

就是345）。

dp[i][j]

表示前

i

个数字划分

j

段的最大值。

具体思路就是要么把这个数带上玩，就是

bk

的末尾加上这个数字，或者单独乘上这个数字，取最大值（代码在最下方）。同时

bk

根据这两种情况更新。

但是我的思路被假了：如果数据是111112，那么在考虑最后一个数字 2 时，显然接在最后一个数上，更新乘积是最优的。

但是两种情况

11 \times 111

和

111 \times 11

都是可以的，明显他们的乘积相同，那么这两种情况该怎么选择呢？我们因为

11 \times 1111 > 111 \times 112

，选择第 2 种。但是程序怎么判定呢？

我就是在这个地方吃亏了，不过骗了 70 pts，CCF 明显脚造数据。现在请求万能的谷民们，这一题有没有正确的

O(n \times k)

的 dp 做法？或者改进一下我的算法，让我的算法能够 AC？

【附】70 pts 代码

前面很长一段是 BigInteger 的板子，请从 435 行开始看起。

CPP

using namespace std;

// begin

struct BigInteger {
	private:
		deque<int> num;
		bool sgn;
		
	public:
		BigInteger operator = (long long init) {
			num.clear();
			if (init) {
				if (init > 0) sgn = true;
				else {
					sgn = false;
					init = -init;
				}
				while (init) {
					num.push_front(init % 10);
					init /= 10;
				}
			} else {
				sgn = true;
				num.push_back(0);
			}
			return *this;
		}
		
		BigInteger operator = (int init) { return (*this = (long long) init); }
		
		BigInteger operator = (const char *s) {
			num.clear();
			assert(*s);
			if (*s == '-') {
				sgn = false;
				assert(*(++s));
			} else sgn = true;
			while (*s) {
				assert(isdigit(*s));
				num.push_back(*(s++) - '0');
			}
			if (num.size() >= 2) assert(num[0]);
			assert(sgn || num[0]);
			return *this;
		}
		
		BigInteger() { *this = 0LL; }
		BigInteger(int init) { *this = init; }
		BigInteger(long long init) { *this = init; } 
		BigInteger(const char *s) { *this = s; }
		BigInteger(string s) { *this = s.c_str(); }
		
		BigInteger operator - () {
			if (num[0] == 0) return *this;
			BigInteger ret = *this;
			ret.sgn = !ret.sgn;
			return ret;
		}
		
		bool operator < (const BigInteger &rhs) const {
			if (sgn != rhs.sgn) return !sgn;
			if (num.size() < rhs.num.size()) return sgn;
			if (num.size() > rhs.num.size()) return !sgn;
			for (int i = 0; i < num.size(); i++)
				if (num[i] != rhs.num[i])
					return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
			return false;
		}
		bool operator < (int rhs) const { return *this < BigInteger(rhs); }
		bool operator < (long long rhs) const { return *this < BigInteger(rhs); }
		bool operator < (const char *rhs) const { return *this < BigInteger(rhs); }
		bool operator < (string rhs) const { return *this < BigInteger(rhs); }
		
		bool operator > (const BigInteger &rhs) const { return rhs < *this; }
		bool operator > (int rhs) const { return *this > BigInteger(rhs); }
		bool operator > (long long rhs) const { return *this > BigInteger(rhs); }
		bool operator > (const char *rhs) const { return *this > BigInteger(rhs); }
		bool operator > (string rhs) const { return *this > BigInteger(rhs); }
		
		bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
		bool operator <= (int rhs) const { return *this <= BigInteger(rhs); }
		bool operator <= (long long rhs) const { return *this <= BigInteger(rhs); }
		bool operator <= (const char *rhs) const { return *this <= BigInteger(rhs); }
		bool operator <= (string rhs) const { return *this <= BigInteger(rhs); }
		
		bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
		bool operator >= (int rhs) const { return *this >= BigInteger(rhs); }
		bool operator >= (long long rhs) const { return *this >= BigInteger(rhs); }
		bool operator >= (const char *rhs) const { return *this >= BigInteger(rhs); }
		bool operator >= (string rhs) const { return *this >= BigInteger(rhs); }
		
		bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
		bool operator == (int rhs) const { return *this == BigInteger(rhs); }
		bool operator == (long long rhs) const { return *this == BigInteger(rhs); }
		bool operator == (const char *rhs) const { return *this == BigInteger(rhs); }
		bool operator == (string rhs) const { return *this == BigInteger(rhs); }
		
		bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
		bool operator != (int rhs) const { return *this != BigInteger(rhs); }
		bool operator != (long long rhs) const { return *this != BigInteger(rhs); }
		bool operator != (const char *rhs) const { return *this != BigInteger(rhs); }
		bool operator != (string rhs) const { return *this != BigInteger(rhs); }
		
		operator bool() {
			return num[0];
		}
		
		operator string() {
			string ret;
			if (!sgn) ret += "-";
			for (int i = 0; i < num.size(); i++) {
				ret += num[i] + '0';
			}
			return ret;
		}
		
		operator int() {
			int ret = 0;
			for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
			return ret;
		}
		
		operator long long() {
			long long ret = 0;
			for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
			return ret;
		}
		
		friend istream& operator >> (istream &in, BigInteger &lhs) {
			string init;
			in >> init;
			lhs = init;
			return in;
		}
		
		friend ostream& operator << (ostream &out, BigInteger lhs) {
			out << (string) lhs;
			return out;
		}
		
		friend BigInteger operator + (BigInteger, BigInteger);
		friend BigInteger operator - (BigInteger, BigInteger);
		friend BigInteger operator * (BigInteger, BigInteger);
		friend BigInteger operator / (BigInteger, BigInteger);
		friend BigInteger operator % (BigInteger, BigInteger);
		
		friend BigInteger operator + (BigInteger lhs, int rhs) { return lhs + BigInteger(rhs); }
		friend BigInteger operator + (BigInteger lhs, long long rhs) { return lhs + BigInteger(rhs); }
		friend BigInteger operator + (BigInteger lhs, const char *rhs) { return lhs + BigInteger(rhs); }
		friend BigInteger operator + (BigInteger lhs, string rhs) { return lhs + BigInteger(rhs); }
		friend BigInteger operator + (int lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
		friend BigInteger operator + (long long lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
		friend BigInteger operator + (const char *lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
		friend BigInteger operator + (string lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
		
		friend BigInteger operator - (BigInteger lhs, int rhs) { return lhs - BigInteger(rhs); }
		friend BigInteger operator - (BigInteger lhs, long long rhs) { return lhs - BigInteger(rhs); }
		friend BigInteger operator - (BigInteger lhs, const char *rhs) { return lhs - BigInteger(rhs); }
		friend BigInteger operator - (BigInteger lhs, string rhs) { return lhs - BigInteger(rhs); }
		friend BigInteger operator - (int lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
		friend BigInteger operator - (long long lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
		friend BigInteger operator - (const char *lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
		friend BigInteger operator - (string lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
		
		friend BigInteger operator * (BigInteger lhs, int rhs) { return lhs * BigInteger(rhs); }
		friend BigInteger operator * (BigInteger lhs, long long rhs) { return lhs * BigInteger(rhs); }
		friend BigInteger operator * (BigInteger lhs, const char *rhs) { return lhs * BigInteger(rhs); }
		friend BigInteger operator * (BigInteger lhs, string rhs) { return lhs * BigInteger(rhs); }
		friend BigInteger operator * (int lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
		friend BigInteger operator * (long long lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
		friend BigInteger operator * (const char *lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
		friend BigInteger operator * (string lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
		
		friend BigInteger operator / (BigInteger lhs, int rhs) { return lhs / BigInteger(rhs); }
		friend BigInteger operator / (BigInteger lhs, long long rhs) { return lhs / BigInteger(rhs); }
		friend BigInteger operator / (BigInteger lhs, const char *rhs) { return lhs / BigInteger(rhs); }
		friend BigInteger operator / (BigInteger lhs, string rhs) { return lhs / BigInteger(rhs); }
		friend BigInteger operator / (int lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
		friend BigInteger operator / (long long lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
		friend BigInteger operator / (const char *lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
		friend BigInteger operator / (string lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
		
		friend BigInteger operator % (BigInteger lhs, int rhs) { return lhs % BigInteger(rhs); }
		friend BigInteger operator % (BigInteger lhs, long long rhs) { return lhs % BigInteger(rhs); }
		friend BigInteger operator % (BigInteger lhs, const char *rhs) { return lhs % BigInteger(rhs); }
		friend BigInteger operator % (BigInteger lhs, string rhs) { return lhs % BigInteger(rhs); }
		friend BigInteger operator % (int lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
		friend BigInteger operator % (long long lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
		friend BigInteger operator % (const char *lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
		friend BigInteger operator % (string lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
		
		BigInteger & operator += (BigInteger rhs) {
			*this = *this + rhs;
			return *this;
		}
		BigInteger & operator += (int rhs) {
			*this = *this + BigInteger(rhs);
			return *this;
		}
		BigInteger & operator += (long long rhs) {
			*this = *this + BigInteger(rhs);
			return *this;
		}
		BigInteger & operator += (const char *rhs) {
			*this = *this + BigInteger(rhs);
			return *this;
		}
		BigInteger & operator += (string rhs) {
			*this = *this + BigInteger(rhs);
			return *this;
		}
		
		BigInteger & operator -= (BigInteger rhs) {
			*this = *this - rhs;
			return *this;
		}
		BigInteger & operator -= (int rhs) {
			*this = *this - BigInteger(rhs);
			return *this;
		}
		BigInteger & operator -= (long long rhs) {
			*this = *this - BigInteger(rhs);
			return *this;
		}
		BigInteger & operator -= (const char *rhs) {
			*this = *this - BigInteger(rhs);
			return *this;
		}
		BigInteger & operator -= (string rhs) {
			*this = *this - BigInteger(rhs);
			return *this;
		}
		
		BigInteger & operator *= (BigInteger rhs) {
			*this = *this * BigInteger(rhs);
			return *this;
		}
		BigInteger & operator *= (int rhs) {
			*this = *this * BigInteger(rhs);
			return *this;
		}
		BigInteger & operator *= (long long rhs) {
			*this = *this * BigInteger(rhs);
			return *this;
		}
		BigInteger & operator *= (const char *rhs) {
			*this = *this * BigInteger(rhs);
			return *this;
		}
		BigInteger & operator *= (string rhs) {
			*this = *this * BigInteger(rhs);
			return *this;
		}
		
		BigInteger & operator /= (BigInteger rhs) {
			*this = *this / rhs;
			return *this;
		}
		BigInteger & operator /= (int rhs) {
			*this = *this / BigInteger(rhs);
			return *this;
		}
		BigInteger & operator /= (long long rhs) {
			*this = *this / BigInteger(rhs);
			return *this;
		}
		BigInteger & operator /= (const char *rhs) {
			*this = *this / BigInteger(rhs);
			return *this;
		}
		BigInteger & operator /= (string rhs) {
			*this = *this / BigInteger(rhs);
			return *this;
		}
		
		BigInteger & operator %= (BigInteger rhs) {
			*this = *this % BigInteger(rhs);
			return *this;
		}
		BigInteger & operator %= (int rhs) {
			*this = *this % BigInteger(rhs);
			return *this;
		}
		BigInteger & operator %= (long long rhs) {
			*this = *this % BigInteger(rhs);
			return *this;
		}
		BigInteger & operator %= (const char *rhs) {
			*this = *this % BigInteger(rhs);
			return *this;
		}
		BigInteger & operator %= (string rhs) {
			*this = *this % BigInteger(rhs);
			return *this;
		}
		
		BigInteger & operator ++ () {
			*this += BigInteger(1);
			return *this;
		}
		
		BigInteger operator ++ (int _) {
			BigInteger tmp(*this);
			*this += BigInteger(1);
			return tmp;
		}
		
		BigInteger & operator -- () {
			*this -= BigInteger(1);
			return *this;
		}
		
		BigInteger operator -- (int _) {
			BigInteger tmp(*this);
			*this -= BigInteger(1);
			return *this;
		}
		
		BigInteger pow(BigInteger n) {
			assert(*this);
			assert(n >= 0);
			if (n == BigInteger(0)) return BigInteger(1);
			BigInteger res = pow(n / BigInteger(2));
			if (n % BigInteger(2)) return res * res * (*this);
			return res * res;
		}
		BigInteger pow(int n) { return pow(BigInteger(n)); }
		BigInteger pow(long long n) { return pow(BigInteger(n)); }
		BigInteger pow(const char *n) { return pow(BigInteger(n)); }
		BigInteger pow(string n) { return pow(BigInteger(n)); }
};

BigInteger operator + (BigInteger lhs, BigInteger rhs) {
	if (lhs.sgn && !rhs.sgn) {
		rhs.sgn = true;
		return lhs - rhs;
	}
	if (!lhs.sgn && rhs.sgn) {
		lhs.sgn = true;
		return rhs - lhs;
	}
	if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
	for (int i = 0; i < rhs.num.size(); i++)
		lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
	for (int i = lhs.num.size() - 1; i > 0; i--) {
		lhs.num[i - 1] += lhs.num[i] / 10;
		lhs.num[i] %= 10;
	}
	if (lhs.num[0] >= 10) {
		lhs.num.push_front(lhs.num[0] / 10);
		lhs.num[1] %= 10;
	}
	return lhs;
}

BigInteger operator - (BigInteger lhs, BigInteger rhs) {
	if (lhs.sgn && !rhs.sgn) {
		rhs.sgn = true;
		return lhs + rhs;
	}
	if (!lhs.sgn && rhs.sgn) return lhs + rhs;
	if (!lhs.sgn && !rhs.sgn) {
		lhs.sgn = true;
		rhs.sgn = true;
		return rhs - lhs;
	}
	if (lhs < rhs) return -(rhs - lhs);
	for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++) 
		lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
	for (int i = lhs.num.size() - 1; i > 0; i--) {
		while (lhs.num[i] < 0) {
			lhs.num[i - 1]--;
			lhs.num[i] += 10;
		}
	}
	while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
	return lhs;
}

BigInteger operator * (BigInteger lhs, BigInteger rhs) {
	deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
	reverse(lhs.num.begin(), lhs.num.end());
	reverse(rhs.num.begin(), rhs.num.end());
	for (int i = 0; i < lhs.num.size(); i++)
		for (int j = 0; j < rhs.num.size(); j++)
			mul[i + j] += lhs.num[i] * rhs.num[j];
	for (int i = 0; i < mul.size() - 1; i++) {
		mul[i + 1] += mul[i] / 10;
		mul[i] %= 10;
	}
	if (mul[mul.size() - 1]) {
		mul.push_back(mul[mul.size() - 1] / 10);
		mul[mul.size() - 2] %= 10;
	}
    while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
	reverse(mul.begin(), mul.end());
	lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
	lhs.num = mul;
	return lhs;
}

BigInteger operator / (BigInteger lhs, BigInteger rhs) {
	assert(rhs);
	BigInteger ret, cnt, div;
	bool sgn = (lhs.sgn ^ rhs.sgn ^ 1);
	rhs.sgn = true;
	div.num.clear();
	for (int i = 0; i < lhs.num.size(); i++) {
		while (!div.num.empty() && div.num[0] == 0) div.num.pop_front();
		div.num.push_back(lhs.num[i]);
		cnt = 0;
		while (div > rhs) {
			div -= rhs;
			cnt++;
		}
		if (div == rhs) {
			div = 0;
			cnt++;
		}
		ret = ret * BigInteger(10) + cnt;
	}
	ret.sgn = sgn;
	return ret; 
}

BigInteger operator % (BigInteger lhs, BigInteger rhs) {
	return lhs - lhs / rhs * rhs;
}

typedef BigInteger BigInt;

// end

char s[100];
BigInt dp[100][100];
BigInt bk[100][100];

int main() {
	int n, k;
	cin >> n >> k >> (s + 1);
	for (int i = 1; i <= n; i++) {
		bk[i][1] = dp[i][1] = dp[i - 1][1] * 10 + s[i] - '0';
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= i; j++) {
			BigInt c1 = dp[i - 1][j - 1] * (s[i] - '0');
			BigInt c2;
			if (bk[i - 1][j] == 0) c2 = 0;
			else c2 = dp[i - 1][j] / bk[i - 1][j] * (bk[i - 1][j] * 10 + s[i] - '0');
			if (c1 >= c2) {
				dp[i][j] = c1;
				bk[i][j] = s[i] - '0';
			} else {
				dp[i][j] = c2;
				bk[i][j] = bk[i - 1][j] * 10 + s[i] - '0';
			}
		}
	}
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
			cout << "bk[" << i << "][" << j << "] = " << bk[i][j] << endl;
		}
	}
	*/
	cout << dp[n][k + 1] << endl;
	return 0;
}

【mxqz】这题有没有 $O(n \times k)$ 的 dp 做法？

讨论操作

回复

相关推荐

【mxqz】这题有没有 $O(n \times k)$ 的 dp 做法？