acmicpc.net 11057(DP), 1937(DP), 10942(DP,팰린드롬)

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

기초 dp

# -*- encoding: cp949 -*-
n=input()
dp = [[0 for i in xrange(10)] for i in xrange(1020)]
for i in xrange(10):
    dp[0][i] = 1
for i in xrange(1,n+1):
    for j in xrange(10):
        for k in xrange(j,10):
            dp[i][j] += (dp[i-1][k]%10007)
            dp[i][j] %= 10007
print dp[n][0]

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

bfs같이 보였었는데 bfs를 쓰면 시간초과난다. 첫 코드는 대나무의 크기 순서대로 정렬한 후

크기 순서대로 방문하면서 조건에 맞는 주위의 대나무들을 bfs로 탐색하면서 +1씩 해주는 거였는데

시간초과났다. 어떻게 할까 생각하다 다른분의 아이디어를 얻었는데 bfs를 쓸필요없이

4방향을 검사후 4방향에서 나보다 작은좌표가 있으면 x,y값 = max(원래값, 작은좌표값+1) 로 처리해주면

된다고 해서 그리 짰더니 됬다.

#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int arr[501][501];
int dp[501][501];
int _y[] = {1,0,-1,0};
int _x[] = {0,-1,0,1};
vector<pair<int ,vector<pair<int, int>>>> s;
 
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			scanf("%d",&arr[i][j]);
			dp[i][j] = 1;
			vector<pair<int, int>> tmp;
			tmp.push_back(make_pair(i,j));
			s.push_back(make_pair(arr[i][j], tmp));
		}
	sort(s.begin(), s.end());

	for(int i=0;i<s.size();i++)
	{
		vector<pair<int, int>> p = s[i].second;
		for(int i=0;i<4;i++)
		{
			int ty = _y[i] + p[0].first;
			int tx = _x[i] + p[0].second;
			if(ty>n-1 || tx>n-1 || ty<0 || tx<0)
				continue;
			if(arr[p[0].first][p[0].second] > arr[ty][tx])
				dp[p[0].first][p[0].second] = max(dp[p[0].first][p[0].second], dp[ty][tx]+1);
		}
	}
	int m = -1;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			m = max(dp[i][j],m);
	printf("%d\n",m);
    return 0;
}

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

팰린드롬. dp[i][j] == [i,j]의 범위의 숫자가 팰린드롬이다. i,j포함.

# -*- encoding: cp949 -*-
import sys
dp = [[0 for j in xrange(2001)] for i in xrange(2001)]
n=int(sys.stdin.readline())
num = map(int,sys.stdin.readline().split())
for i in xrange(n-1,-1,-1):
    for j in xrange(i,n):
        if i==j: dp[i][j] = 1
        elif i==j-1 and num[i]==num[j]: dp[i][j] = 1
        elif dp[i+1][j-1]==1 and num[i]==num[j]: dp[i][j] = 1

for m in xrange(input()):
    s,e=map(int,sys.stdin.readline().split())
    print 1 if dp[s-1][e-1]==1 else 0