hdu-4597(๊ฒŒ์ž„ DP)

์ด ๋ฌธ์ œ๋Š” dp๋กœ ๋ฐ”๋‘‘ ๋ฌธ์ œ๋ฅผ ์œ ๋„ํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์ด๋‹ค. ์ž์„ธํžˆ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ์ด๊ฒƒ์€ ์‚ฌ์‹ค ๊ตฌ๊ฐ„ ์ฒ˜๋ฆฌ ๋ฌธ์ œ์ด๊ณ  ์ผ๋ฐ˜์ ์ธ ๊ตฌ๊ฐ„ ๋ฌธ์ œ๋Š” ๋น„๊ต์  ๊ฐ„๋‹จํ•œ ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.
๋‘ ์•„์ด๊ฐ€ ๋ชจ๋‘ ๋˜‘๋˜‘ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋“ค์€ ๋ฐ˜๋“œ์‹œ ๊ฐ€๋Šฅํ•œ ํ•œ ์ตœ์„ ์˜ ๋ฐฉ์•ˆ์„ ์„ ํƒํ•  ๊ฒƒ์ด๋‹ค. ๊ทธ๋ž˜์„œ ๋ชจ๋“  ์‚ฌ๋žŒ์˜ ํ˜„์žฌ์˜ ์ตœ์„ ์€ ๋‹ค์Œ ์‚ฌ๋žŒ์˜ ์ตœ์„ ์— ์˜์กดํ•œ๋‹ค.๊ทธ๋Ÿผ ๋””ํ…Œ์ผ์€ ์–ด๋–ป๊ฒŒ ํ• ๊นŒ์š”?์•„๋‹ˆ๋ฉด ์ผ€์ผ€๋ฌต์€ ๊ณก์กฐ๋ฅผ ๋‹ค์‹œ ์—ฐ์ฃผํ• ์ง€, ๋จผ์ € ์ƒํƒœ๋ฅผ ์–ด๋–ป๊ฒŒ ํ‘œ์‹œํ• ์ง€, ์ƒํƒœ๋ฅผ ์–ด๋–ป๊ฒŒ ์˜ฎ๊ธธ์ง€ ์ƒ๊ฐํ•ด ๋ณด์ž.
์ƒํƒœ๋ฅผ ์™„์ „ํ•˜๊ฒŒ ๋ฌ˜์‚ฌํ•˜๋ ค๋ฉด, ์šฐ๋ฆฌ๋Š” ๋ฐ˜๋“œ์‹œ 4์ฐจ์› ๊ทธ๋ฃน์„ ๋งŒ๋“ค์–ด ๋‘ ๋ฌด๋”๊ธฐ์˜ ํ˜„์žฌ ์ƒํƒœ๋ฅผ ๊ธฐ๋กํ•ด์•ผ ํ•œ๋‹ค.๊ทธ๋Ÿฌ๋ฉด ์ƒํƒœ๋Š” d[al][ar][bl][br]๋กœ ํ‘œ์‹œํ•˜๊ธฐ ์–ด๋ ต์ง€ ์•Š๋‹ค. ๋‘ ๋ฌด๋”๊ธฐ์˜ ์นด๋“œ๊ฐ€ ํ˜„์žฌ ์ˆ˜๋ฏธ ์ƒํ™ฉ์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ์ƒํƒœ๋Š” ์–ด๋–ป๊ฒŒ ์ด๋™ํ•ฉ๋‹ˆ๊นŒ?
์•ž์—์„œ ๋งํ–ˆ๋“ฏ์ด ํ˜„์žฌ์˜ ์ตœ์šฐํ•ด๋Š” ์ด์ „์˜ ์ตœ์šฐํ•ด์— ์˜์กดํ•œ๋‹ค. ์™œ๋ƒํ•˜๋ฉด ๋‘ ์•„์ด๊ฐ€ ๋ชจ๋‘ ๋˜‘๋˜‘ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.์ถ”DP๋Š” ํ•ญ์ƒ ์ปจ๋””์…˜์ด ๋ฌด์—‡์„ ํ‘œ์‹œํ•˜๋Š”์ง€ ์ฃผ์˜ํ•ด์•ผ ํ•œ๋‹ค. ๋ฐฉ๊ธˆ ์ด ์•„์ด์˜ ์ตœ๋Œ€ ์ ์ˆ˜๋ฅผ ํ‘œ์‹œํ•œ๋‹ค๊ณ  ํ–ˆ๋Š”๋ฐ ์–ด๋–ป๊ฒŒ ๊ตฌํ•˜์ง€?๋ถ„๋ช…ํžˆ ์ด์ ์—์„œ ๋‹ค์Œ ์•„์ด์˜ ๋“์ ์„ ๋นผ๊ณ  ๋‹ค์Œ ์•„์ด์˜'์ด์ '์€ ํ˜„์žฌ ์•„์ด๊ฐ€ ๊ฐ€์ ธ๊ฐ„ ํŒจ๋ฅผ ๋นผ์•ผ ํ•œ๋‹ค.
์ž์„ธํ•œ ์ฐธ๊ณ  ์ฝ”๋“œ:
#include
using namespace std;
int T,n,d[25][25][25][25],a[25],b[25];
int dp(int al,int ar,int bl,int br,int sum) {
    int& ans = d[al][ar][bl][br];
    if(ans != -1) return ans;
    ans = 0;
    if(al<=ar) {
        ans = max(ans,sum-dp(al+1,ar,bl,br,sum-a[al]));
        ans = max(ans,sum-dp(al,ar-1,bl,br,sum-a[ar]));
    }
    if(bl<=br) {
        ans = max(ans,sum-dp(al,ar,bl+1,br,sum-b[bl]));
        ans = max(ans,sum-dp(al,ar,bl,br-1,sum-b[br]));
    }
    return ans;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int sum = 0;
        memset(d,-1,sizeof(d));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]) , sum += a[i];
        for(int i=1;i<=n;i++) scanf("%d",&b[i]) , sum += b[i];
        int ans = dp(1,n,1,n,sum);
        printf("%d
",ans); } return 0; }

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ