M-Geeker技术竞赛
第一题把数字拆分成三个数字,然后三个数字对应的字符串串起来,然后倒着找不为0的位置,从这个位置倒着开始输出,但是不知道哪里错了,0.85,求告知!
第二题输出abab...cdefg...这样子的字符串就行了,特殊情况判定一下。
第三题用暴力dp了一下,0.7,有没有大佬会做的,教我一下呀!
我是dp[i][cnt]表示当前数字i拆分cnt次能够获得的最大值,dp[i][cnt] = max(dp[j][k]+dp[i-j][cnt-1-k]+j*(i-j))
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int s; long long m; long long dp[1010][1010]; int main() { cin >> s >> m; memset(dp, 0, sizeof dp); int cnt; for (cnt = 1; cnt < s; cnt++){ for (int i = 2; i <= s; i++) for (int j = 1; j < i; j++) for (int k = 0; k < cnt; k++) dp[i][cnt] = max(dp[i][cnt], dp[j][k]+dp[i-j][cnt-1-k]+j*(i-j)); if (dp[s][cnt] >= m) break; } if (cnt == s) cout << "-1" << endl; else cout << cnt << endl; return 0; }