区间DP – hahaschool

题意

给出了一个算术表达式，表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算，运算结果放回式子中继续进行运算，直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义，注意到题目中讲到只要有一轮选取的数字不一样，就视为不同。这句话的含义中有两个信息：一是允许重复，二是要分先后。

思路

最开始确实是没什么思路的，后来看了看board发现并不是特别难的题。于是尝试拆解问题，我们可以从算数式的一小段入手，以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分，只有一种配置方法，就是(1 + 4);
考虑1 + 4 * 6部分，我们发现这一部分可以看成两种情况：1 + (4 * 6)和(1 + 4) * 6，在这里面我们已经考虑了1 + 4区段，而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段，要想得到这个区段的全部情况，我们应该考虑：
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况，其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况，而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后，考虑1 + 4 * 6 – 8 * 3，顺着上面的思路来，就可以拆分成：
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3，接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了，在推方程的时候，我们是将所有子情况的答案累加，得到当前情况的答案，但这还不够，还要注意每种情况，因为选择顺序的关系，会有多重副本，而这个副本的数量其实蛮好求，就是阶乘，而还要注意，我们在讨论当前情况的时候，是将整个等待处理的算式区段分成了（左区段）算子（分界点）算子（右区段）这样看待的，那么先后的问题又来了，我们不光左右区段的答案自身要乘上阶乘，最后整个结果还要乘上一个组合数，因为左右区段的操作又是分先后的。

以下引自官方题解，注意第2段第2行的dp[l][r]实际上是dp[l][k]。

代码

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define MODER 1000000007
#define MAXN 105
long long seq[MAXN];
long long fac[MAXN];
long long C[MAXN][MAXN];
string op;
int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){
    if (_op == '+') {
        return a+b;
    }
    if (_op == '-') {
        return a-b;
    }
    if (_op == '*') {
        return a*b;
    }
    return 0;
}

void solve(){
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = seq[i];
    }
    for (int j = 1; j <= n; j++) {
        for (int i = j - 1; i >= 1; i--) {
            for (int k = i; k < j; k++) {
                if (op[k-1] == '*') {
                    dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }else{
                    dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }
                dp[i][j] %= MODER;
            }
        }
    }
    cout << (dp[1][n]+MODER)%MODER << endl;
}

int main(){
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        fac[i] = fac[i-1] * i;
        fac[i] %= MODER;
    }
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;
        }
    }
    while (scanf(" %d",&n) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf(" %lld",&seq[i]);
        }
        cin >> op;
        solve();
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

#define MODER 1000000007

#define MAXN 105

long long seq[MAXN];

long long fac[MAXN];

long long C[MAXN][MAXN];

string op;

int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){

if (_op == '+') {

return a+b;

}

if (_op == '-') {

return a-b;

}

if (_op == '*') {

return a*b;

}

return 0;

}

void solve(){

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; i++) {

dp[i][i] = seq[i];

}

for (int j = 1; j <= n; j++) {

for (int i = j - 1; i >= 1; i--) {

for (int k = i; k < j; k++) {

if (op[k-1] == '*') {

dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}else{

dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}

dp[i][j] %= MODER;

}

cout << (dp[1][n]+MODER)%MODER << endl;

}

int main(){

fac[0] = 1;

fac[1] = 1;

for (int i = 2; i < MAXN; i++) {

fac[i] = fac[i-1] * i;

fac[i] %= MODER;

}

for (int i = 0; i < MAXN; i++) {

C[i][0] = C[i][i] = 1;

for (int j = 1; j < i; j++) {

C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;

}

while (scanf(" %d",&n) != EOF) {

for (int i = 1; i <= n; i++) {

scanf(" %lld",&seq[i]);

}

cin >> op;

solve();

}

return 0;

}

测试数据

97
42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517
*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*
100
325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288
+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*
90
956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566
++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-
98
465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729
-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+
90
350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153
**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++
91
369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648
+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+
95
485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733
++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*
90
708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957
+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++
96
745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147
**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---
94
879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038
*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517

*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*

100

325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288

+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*

956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566

++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-

465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729

-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+

350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153

**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++

369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648

+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+

485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733

++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*

708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957

+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++

745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147

**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---

879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038

*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

302477149

455689444

197787710

802805207

652251842

492754358

934589866

940842836

821057755

931125012

Tag: 区间DP

LA4394 String Painter

题意

思路

代码

POJ 2955 Brackets

题意

思路

代码

HDU5396 / 15多校9-1 Expression

题意

注意

思路

代码

测试数据