求大佬看看为什么我的dp + __int128只有70pt
查看原帖
求大佬看看为什么我的dp + __int128只有70pt
1217892
cxjy楼主2024/11/22 19:02

我的转移方程是这样的,用 t[i][j] 记录 前 i 个字符 j 个乘号中最后一个乘号的下标, 然后 a[i][j] 代表前i个字符加上j个乘号的最大值, 转移方程是:

a[i][j]=max⁡(a[i−1][j−1]∗(s[i]−′0′),a[i−1][j]∗10+(s[i]−′0′)∗a[t[i−1][j]][j−1](t[i−1][j]≠0时)); a[i][j] =\max(a[i-1][j-1]*(s[i]-'0'),a[i-1][j]*10+(s[i]-'0')*a[t[i-1][j]][j-1](t[i-1][j]\neq 0 时)); 其中当j=0时另外算,a[i][0]=a[i−1][0]∗10+s[i]−′0′;其中当j=0时另外算, a[i][0] = a[i-1] [0]*10+s[i]-'0';
2024/11/22 19:02