Вкошп 2020-2021

Информатика
1

Решал Ашку ВКОШП 2020-2021. Додумался до идеи, что нужно брать только горизонтальные пути на некую сумму и вертикальные пути на оставшеюся сумму и наоборот. Написал рюкзак, но как считать количество уникальных клеток? Если sum - это сумма всех элементов массива и можно получить сумму w, то нужно закрасить w горизонтальных клеток и sum-w вертикальных и наоборот, поэтому некоторые клетки красятся несколько раз. Почитал разбор, но не понял.

void solve(){
    cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	dp[0][0] = 1;

	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= w; j++){
			if(a[i] <= j)
				dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
			else
				dp[i][j] = dp[i-1][j];	
		}
	}
	for(int i = 1; i <= w; i++){//w = 1e6
		if(dp[n][i]){
			//smth
		}
	}
}
2

Это не ВКОШП 2020, а отбор на ВКОШП 2020

@fractal ты же решал её тогда, объясни

1 лайк
3

Оказ есть скринкаст, там с 2:59:25 до 3:45:30 мы решаем её и обсуждаем идеи

5 лайков
4

Твой рюкзак просто считает доступную сумму, эта сумма может быть получена как вертикально, так и горизонтально. Как и сказанно в разборе давай сначала нарисуем вертикальные линии от горизонтальных сумм(т.е для каждого такого x, что dp_n_x = 1, отложим вверх sum - x). Затем, как я сказал ранее все суммы могут быть получены как горизонтально так и вертикально, таким образом попробуй нарисовать горизонтальные линии уже от вертикальных отметок и посмотри до куда они доходят

После того как добавим длину всех вертикальным столбцов(sum - x), давай будем пробегаться по вертикальным столбцам, т.е по таким x, что dp[n][x] = 1, от вершины этого столбца будет исходить одна линия влево, давай просто все клетки в этой линии добавим в ответ. Интересное замечание, ты получил все клетки, осталось только удалить исключения. Каждый раз добавляя линию ты точно знаешь сколько будет пересечений с уже добавленными клетками(т.е вертикальными столбцами), а именно если это первый вертикальный столбец(самый высокий и самый левый, где x наименьший) то тогда будет только 1 пересечение в вершине столбца. Если 2ой, то 2 - в вершине текущего столбца и в предыдущем на той же высоте, если 3 то 3 и т.д. Можешь фором пробежаться, а можешь просто математически ответ посчитать

6 лайков
5

Спасибо!

1 лайк