알얼알/0514 - Revision history

219.255.207.62 at 08:18, 15 May 2018

2018-05-15T08:18:25Z

@@ Line 20: / Line 20: @@
   dp[i][j] : i번째 단계에 j번째 칸에 도착하는 경우의 최대값
-  dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + val[i][1]
+  dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + arr[i][1]
-  dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + val[i][2]
+  dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2]
-  dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + val[i][3]
+  dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + arr[i][3]
   최소값은 MAX를 MIN으로 바꾸고 똑같이 하면 됨.
@@ Line 134: / Line 134: @@
 ==== 옥상 정원 꾸미기 ====
 [[File:ex.png]]
 ==== Combinations ====
@@ Line 140: / Line 180: @@
 (A*B)%C = ((A%C)*(B%C))%C 라는 모듈러 분배법칙도 알고 있어야 합니다.
 주의할 점은 모듈러 분배법칙이 나눗셈에 대해선 성립하지 않습니다!
   dp[n][k] = (dp[n-1][k] + dp[n-1][k-1]) % MOD

imported>njw1204 at 07:57, 15 May 2018

2018-05-15T07:57:23Z

@@ Line 134: / Line 134: @@
 ==== 옥상 정원 꾸미기 ====
 [[File:ex.png]]
 -----------------------------------
 [[알얼알]]

imported>njw1204 at 07:36, 15 May 2018

2018-05-15T07:36:52Z

@@ Line 58: / Line 58: @@
 ==== 카잉 달력 ====
   for _ in range(int(input())):
     m,n,x,y=map(int,input().split())
@@ Line 86: / Line 89: @@
     print(ans)
 -----------------------------------
 [[알얼알]]

imported>njw1204: {CREATE}

2018-05-15T07:00:19Z

{CREATE}

New page

__TOC__
=== 문제 ===
* [https://www.acmicpc.net/problem/1402 아무래도이문제는A번난이도인것같다]
* [https://www.acmicpc.net/problem/15645 내려가기 2]
* [https://www.acmicpc.net/problem/6064 카잉 달력]
* [https://www.acmicpc.net/problem/2606 바이러스]
* [https://www.acmicpc.net/problem/6198 옥상 정원 꾸미기]
* [https://www.acmicpc.net/problem/7579 앱]
* [https://www.acmicpc.net/problem/13239 Combinations]

=== 해설 ===
==== 아무래도이문제는A번난이도인것같다 ====
N = N * (-1) * (-1) * (-1) * (-1) * ... 으로 음의 무한대까지 만들고
N = N * 1 * 1 * 1 * 1 * ... 으로 양의 무한대까지 만들 수 있다.
print('yes\n'*int(input()))

==== 내려가기 2 ====
다이나믹 프로그래밍으로 풀립니다.
시간 복잡도는 O(n)
dp[i][j] : i번째 단계에 j번째 칸에 도착하는 경우의 최대값

dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + val[i][1]
dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + val[i][2]
dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + val[i][3]

최소값은 MAX를 MIN으로 바꾸고 똑같이 하면 됨.

#include <iostream>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX3(x,y,z) MAX(MAX(x,y),z)
#define MIN3(x,y,z) MIN(MIN(x,y),z)
using namespace std;

int arr[100001][4];
int dp[100001][4][2];

int main() {
int N;
cin >> N;

for (int i = 1; i <= N; i++)
cin >> arr[i][1] >> arr[i][2] >> arr[i][3];

for (int i = 1; i <= N; i++) {
dp[i][1][0] = MIN(dp[i-1][1][0], dp[i-1][2][0]) + arr[i][1];
dp[i][2][0] = MIN3(dp[i-1][1][0], dp[i-1][2][0], dp[i-1][3][0]) + arr[i][2];
dp[i][3][0] = MIN(dp[i-1][2][0], dp[i-1][3][0]) + arr[i][3];
dp[i][1][1] = MAX(dp[i-1][1][1], dp[i-1][2][1]) + arr[i][1];
dp[i][2][1] = MAX3(dp[i-1][1][1], dp[i-1][2][1], dp[i-1][3][1]) + arr[i][2];
dp[i][3][1] = MAX(dp[i-1][2][1], dp[i-1][3][1]) + arr[i][3];
}

cout << MAX3(dp[N][1][1], dp[N][2][1], dp[N][3][1]) << ' ';
cout << MIN3(dp[N][1][0], dp[N][2][0], dp[N][3][0]);
return 0;
}

==== 카잉 달력 ====
for _ in range(int(input())):
m,n,x,y=map(int,input().split())
if not (1<=x<=m and 1<=y<=n):
print(-1)
continue

if m<n:
m,n=n,m
x,y=y,x

i=x
if x<=n:
j=x
else:
j=(x-1)%n+1

ans,first_j=i,j
while i-j!=x-y:
j+=m-n
if j>n:
j=(j-1)%n+1
if j==first_j:
ans=-1
break
ans+=m

print(ans)

-----------------------------------
[[알얼알]]