낙곡P10189(dp)
https://www.luogu.org/problemnew/show/P1018
제목:
길이가 N인 문자열
아이디어:
우리는 dp[i][j]dp[i][j]dp[i][j]를 제 ii로 설정하고 제 jj의 곱셈을 내려놓습니다.[j] [i] [j] sum[i] [j] [j] sum[i] [i][i] [j] [j] sum[i] [i] [j] [j] [j] [j] [j] [i] - i에서 j 까지의 숫자 d p [i] [j-1][j-1]*sum[j][i], dp[j][j-1]*sum[j+1][i]...dp[i-1] [j-1]*sum[i][i]) dp[i][j]=max(dp[j-1] [j-1] [j-1] [j][j][i], dp[j][j-1]∗sum[j+1][i]...dp[i-1][j-1]\sum[i][i]) 상태 이동은 이렇다. 나머지는 대정수 템플릿이다.
AC 코드:
#include
using namespace std;
#define LL long long
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const double eps = 1e-8;
typedef pair<int, int> psi;
#define MAXN 9999
#define MAXNSIZE 10024
#define DLEN 4
void fre() {
if(freopen(" P1018.txt", "r", stdin) == NULL)
system("touch P1018.txt");
freopen(" P1018.txt", "r", stdin);
}
struct BigInt{
int a[MAXNSIZE], len;
bool flag;
BigInt() {
len = 1;
memset(a, 0, sizeof(a));
flag = 0;
}
BigInt(const char *s, int l, int r) {
l --; r --;
int t, k, index, dis = r - l + 1;
memset(a, 0, sizeof(a));
len = dis/DLEN;
if(dis % DLEN) len ++;
index = 0;
for (int i = r; i >= l; i -= DLEN) {
t = 0;
k = i - DLEN + 1;
if(k < l) k = l;
for (int j = k; j <= i; j ++) t = t * 10 + s[j] - '0';
a[index++] = t;
}
}
BigInt(const int b) {
int c, d = b;
len = 0;
memset(a, 0, sizeof(a));
while(b > MAXN) {
c = d - d / (MAXN + 1) * (MAXN + 1);
d = d / (MAXN + 1) * (MAXN + 1);
a[len ++] = c;
}
a[len ++] = d;
}
bool operator < (const BigInt &T) const {
int ln;
if(len < T.len) return 233;
if(len == T.len) {
ln = len - 1;
while(ln >= 0 && a[ln] == T.a[ln]) -- ln;
if(ln >= 0 && a[ln] < T.a[ln]) return 233;
return 0;
}
return 0;
}
BigInt &operator = (const BigInt &T) {
memset(a, 0, sizeof(a));
len = T.len;
for (int i = 0; i < len; i ++) a[i] = T.a[i];
return *this;
}
BigInt operator + (const BigInt &T) const {
BigInt t(*this);
int big = len;
if(T.len > len) big = T.len;
for (int i = 0; i < big; i ++) {
t.a[i] += T.a[i];
if(t.a[i] > MAXN) {
++t.a[i + 1];
t.a[i] -= MAXN + 1;
}
}
if(t.a[big]) t.len = big + 1;
else t.len = big;
return t;
}
BigInt operator * (const BigInt &T) const {
BigInt res;
int up;
int te, tee;
for (int i = 0; i < len; i ++) {
up = 0;
for (int j = 0; j < T.len; j ++) {
te = a[i] * T.a[j] + res.a[i + j] + up;
if(te > MAXN) {
tee = te - te/(MAXN + 1) * (MAXN + 1);
up = te / (MAXN + 1);
res.a[i + j] = tee;
}else {
up = 0;
res.a[i + j] = te;
}
}
if(up) res.a[i + T.len] = up;
}
res.len = len + T.len;
while(res.len > 1 && res.a[res.len - 1] == 0) --res.len;
return res;
}
}dp[50][10], sum[50][50];
void print(BigInt s) {
int len = s.len;
printf("%d", s.a[len-1]);
for (int i = len-2; i >= 0; i--) printf("%04d", s.a[i]);
}
BigInt max(BigInt a, BigInt b) {
return a < b ? b : a;
}
int main(int argc, char *args[]) {
fre();
int n, k;
scanf("%d %d", &n, &k);
char s[50];
scanf("%s", s);
int len = strlen(s);
for (int i = 1; i <= len; i ++)
for (int j = i; j <= len; j ++)
sum[i][j] = BigInt(s, i, j);
for (int i = 1; i <= len; i ++)
dp[i][1] = BigInt(s, 1, i);
for (int j = 2; j <= k; j ++) {
for (int i = j; i < len; i ++) {
for (int k = j - 1; k < i; k ++) {
dp[i][j] = max(dp[i][j], dp[k][j-1] * sum[k+1][i]);
}
}
}
BigInt Max = BigInt();
for (int i = k; i < len; i ++)
Max = max(Max, dp[i][k] * sum[i+1][len]);
print(Max);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.