acmicpc.net 1480(배낭 문제, DP, 비트마스크), 5557(DP, 조합), 2630(분할 정복)

https://www.acmicpc.net/problem/1480

와 미친.. dp 왜이렇게 재밌는지 모르겠다 이 문제는 배낭 문제+비트마스크다. 가장 큰 문제는

가방이 여러개라는거다. 처음에는 가방 1에서 모을수있는만큼 최대한 보석을 모으고 그 목록을 따로

저장 후 다음 가방으로. 이런식이었는데 이렇게 하면 안된다. 각각의 최댓값이 전체 문제의 최댓값이

안 될수도 있기 때문이다. 따라서 모든 경우의 수를 조합해야된다. 보석 수나 가방 용량 등을 봤을때

수가 적어서 모든 수를 조합하고 적당히 메모이제이션 하면 잘 나올거라고 예측 가능하다.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)

def getmax(m, capacity, jewlery):
    global c
    #print m,capacity
    ret = dp[m][capacity][jewlery]
    if ret != 0: return ret

    for i in xrange(n):
        if capacity >= weight[i] and (jewlery & (1<<i)==0):
            dp[m][capacity][jewlery] = max(dp[m][capacity][jewlery], getmax(m, capacity-weight[i], jewlery | (1<<i)) + 1)
        elif capacity < weight[i] and m > 0 and c>=weight[i] and (jewlery & (1<<i)==0):
            dp[m][capacity][jewlery] = max(dp[m][capacity][jewlery], getmax(m-1, c-weight[i], jewlery | (1<<i)) + 1)

    return dp[m][capacity][jewlery]

n,m,c = map(int,raw_input().split())
weight = sorted(map(int,raw_input().split()))
dp = [[[0 for k in xrange(2**n)] for j in xrange(c+1)] for i in xrange(m+1)]
print getmax(m-1, c, 0)

https://www.acmicpc.net/problem/5557

신들렸나 갑자기 문제가 잘풀린다.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(10000000)
def formula(answer, index):
    if answer>20 or answer<0 or index==n:
        return 0
    if index==n-1 and answer==num[index]:
        dp[index][answer] = 1
        return 1

    ret = dp[index][answer]
    if ret!=0: return ret
    
    dp[index][answer] += formula(answer-num[index], index+1)
    dp[index][answer] += formula(answer+num[index], index+1)

    return dp[index][answer]

n=input()
num = map(int,raw_input().split())
dp = [[0 for i in xrange(1050)] for j in xrange(220)]
print formula(num[0],1)

https://www.acmicpc.net/problem/2630

앞에 분할정복 문제인 쿼드트리랑 똑같다.

# -*- encoding: cp949 -*-
import sys
b,w = 0,0
def quad(x1, y1, x2, y2):
    global b,w
    flag = False
    for i in xrange(y1, y2+1):
        for j in xrange(x1, x2+1):
            if maps[y1][x1] != maps[i][j]:
                flag = True
                break
        if flag: break
    if not flag:
        if maps[y1][x1]=='0':
            w += 1
        else:
            b += 1
    if flag:
        h_x = (x1+x2)/2; h_y = (y1+y2)/2
        quad(x1, y1, h_x, h_y)
        quad(h_x+1, y1, x2, h_y)
        quad(x1, h_y+1, h_x, y2)
        quad(h_x+1, h_y+1, x2, y2)
 
n = input()
maps = [raw_input().split() for i in xrange(n)]
quad(0,0,n-1,n-1)
print w
print b