Difference between r1.1 and the current
@@ -3,7 +3,7 @@
= 오늘의 문제 =
* [https://www.acmicpc.net/problem/11659|구간 합 구하기 4]
* [https://www.acmicpc.net/problem/2042|구간 합 구하기]
* 15이원준
* [https://www.acmicpc.net/problem/11659|구간 합 구하기 4]
* [https://www.acmicpc.net/problem/2042|구간 합 구하기]
* [https://www.acmicpc.net/problem/2240|자두나무]
= 참가자 =* 15이원준
@@ -183,13 +183,50 @@
}
}}}
== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
== 곽정흠 ==
}}}
=== 자두나무 ===
{{{
#include<iostream>
#include<algorithm>
using namespace std;
int arr[32][1001] = {0,};
int ina[1001] = {0,};
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i<=n; i++){
scanf("%d", &ina[i]);
}
int place = 1;
for(int i = 1; i<=m+1; i++){
for(int j = 1; j<=n; j++){
int tmp = arr[i][j-1];
if(ina[j] == place){
tmp++;
}
arr[i][j] = max(tmp, arr[i-1][j]);
}
if(i%2){
place = 2;
}
else{
place = 1;
}
}
cout<<arr[m+1][n];
}
}}}
== 박인서 ==== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
* 구간합은 Binary Indexed Tree를 사용했습니다.
* 자두나무는 dp로 풀었습니다.(냅색을 약간 응용했습니다.)
== 박인서 ==== 곽정흠 ==
3.1.1. 구간 합 구하기 4 ¶
#include<iostream>
using namespace std;
long long int arr[4000000] = { 0, };
int start = 1;
int sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[(p+1)*2];
}
else{
arr[p] = arr[n] + arr[(p+1)*2 - 1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}
int main(){
int n,m,k;
cin>>n>>m;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);
for(int i = 0; i< m; i++){
int tmp1, tmp2;
scanf("%d %d", &tmp1, &tmp2);
printf("%lld\n", sum(start-1 + tmp1, start-1+tmp2));
}
}
3.1.2. 구간 합 구하기 ¶
#include<iostream>
using namespace std;
long long int arr[4000000] = { 0, };
int start = 1;
void sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[n+1];
}
else{
arr[p] = arr[n] + arr[n-1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);
for(int i = 0; i< m+k; i++){
int tmp1, tmp2, tmp3;
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
if(tmp1 == 1){
arr[start + tmp2 -1] = tmp3;
sort(start + tmp2 -1);
}
else{
printf("%lld\n", sum(start-1 + tmp2, start-1+tmp3));
}
}
}
3.1.3. 자두나무 ¶
#include<iostream>
#include<algorithm>
using namespace std;
int arr[32][1001] = {0,};
int ina[1001] = {0,};
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i<=n; i++){
scanf("%d", &ina[i]);
}
int place = 1;
for(int i = 1; i<=m+1; i++){
for(int j = 1; j<=n; j++){
int tmp = arr[i][j-1];
if(ina[j] == place){
tmp++;
}
arr[i][j] = max(tmp, arr[i-1][j]);
}
if(i%2){
place = 2;
}
else{
place = 1;
}
}
cout<<arr[m+1][n];
}
