acmicpc.net 1927,11279,11286(힙), 11055(LIS), 1956(플로이드)

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

최소 힙.

# -*- encoding: cp949 -*-
from heapq import *
h = []
for n in xrange(input()):
    x=input()
    if x==0:
        if len(h)==0:
            print 0
        else:
            print heappop(h)
    else:
        heappush(h,x)
    

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

위는 최소 힙. 이번문제는 최대 힙이다. 파이썬에는 최대 힙이 구현되어 있지 않다.

어떻게 할까..? 스택오버플로우에서 봤는데 어떤분이 '최소 힙을 사용하되, 숫자를 넣을때 -로 넣고

뺄때 -를 붙이면 최대 힙이 되!' 라는 답글을 보고 천재라고 생각했다.....

# -*- encoding: cp949 -*-
from heapq import *
h = []
for n in xrange(input()):
    x=input()
    if x==0:
        if len(h)==0:
            print 0
        else:
            print -heappop(h)
    else:
        heappush(h,-x)

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

그러면 절대값 힙은 어떻게 구현할까..? 아래 코드처럼 리스트로 만들어서 보관하면 된다.

# -*- encoding: cp949 -*-
from heapq import *
h = []
for n in xrange(input()):
    x=input()
    if x==0:
        if len(h)==0:
            print 0
        else:
            print heappop(h)[1]
    else:
        heappush(h,[abs(x),x])

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

변형된 LIS문제다. 가장 큰 증가 부분 수열을 찾으랜다. 아래처럼 고쳐주면 된다.

# -*- encoding: cp949 -*-
dp = [0 for i in xrange(1001)]
def lis(s):
    if dp[s+1] != 0: 
        return dp[s+1]
    if s+1<n:
        dp[s+1] = 0

    for i in xrange(s+1,n):
        if s== -1 or arr[s] < arr[i]:
            dp[s+1] = max(dp[s+1], lis(i) + arr[i])
    return dp[s+1]
 
n = input()
arr = map(int,raw_input().split())
print lis(-1)

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

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

int n,m,v,a,b,c;
long long w[402][402];
long long INF = 99999999999;

void floyd()
{
	for(int k=1;k<n+1;k++)
		for(int i=1;i<n+1;i++)
			for(int j=1;j<n+1;j++)
				if(w[i][j] > w[i][k]+w[k][j])
					w[i][j] = w[i][k]+w[k][j];
}


int main()
{
	ios::sync_with_stdio(false); 
	cin>>n>>m;
	for(int i=1;i<n+1;i++)
		for(int j=1;j<n+1;j++)
			w[i][j] = INF;

	for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		w[a][b] = c;
	}

	floyd();
	//cout<<"\n";
	//for(int i=1;i<n+1;i++)
	//{
	//	for(int j=1;j<n+1;j++)
	//		cout<<w[i][j]<<" ";
	//	cout<<endl;
	//}
	long long short_way = INF;
	for(int i=1;i<n+1;i++)
		if(w[i][i]!=INF && short_way > w[i][i])
			short_way = w[i][i];
	if(short_way!=INF)
		cout<<short_way<<"\n";
	else
		cout<<-1<<"\n";
	return 0;
}