Список вопросов
Страна замов. Напишите программу на Python
10th December, 18:14
410
0
На листе клетчатой бумаги рисуют выпуклый 100-угольник с вершинами в узлах сетки. Какое наибольшее число диагоналей этого 100-угольника может идти по линиям сетки?
7th November, 15:29
267
0
Рассмотрим все прямоугольники, длины сторон которых выражены целым числом метров, и периметр которых (в метрах) численно равняется площади (в метрах квадратных). Найдите суммарную площадь всех таких, разных по размеру сторон, прямоугольников.Прямоугольники, отличающиеся порядком сторон, например, 10 * 20 и 20 * 10 считаем одинаковыми.
7th October, 20:57
741
0
Кто и за сколько может написать программу управления курсором?
2nd October, 23:48
501
3
Как авторизоваться на novafilm.tv при помощи cURL?
2nd October, 23:33
381
3
Верстка, position:relative создает пустое место
2nd October, 23:31
324
2
Что улучшить в переводе Apache Public License?
2nd October, 23:29
329
1
Формирование кода видео Вконтакте
2nd October, 23:23
401
3
IPad2 с 3G из Штатов?
2nd October, 23:18
373
5
А будет ли tcpdump видеть ack flood?
2nd October, 23:14
290
2
Альфа банк и странное смс мошенничество?
2nd October, 23:05
665
6
Софт для "ремонта" поврежденного h264 видео?
2nd October, 22:55
301
3
Scrapy — Python
2nd October, 22:54
313
4
Помощь с доставкой из США?
2nd October, 22:47
339
3
Создание stop-motion ролика
2nd October, 22:41
374
5
Верстка ul/li в несколько колонок?
2nd October, 22:41
275
13
Существует ли поисковик, отсортированный по дате?
2nd October, 22:32
309
3
Вопрос к пользователям HTC HD7?
2nd October, 22:32
330
2
Как получить путь к аватару пользователя когда он авторизируется на сайте через openid google?
2nd October, 22:20
345
2
Что случилось с Кенгуру.ТВ?
2nd October, 22:19
380
3
Решение задачи Игра с монетами с Меньшиков
Без пояснения   Просмотров: 164
Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.
Код
#include #include #include using namespace std; #define USE_VECTOR #ifdef USE_VECTOR vector > keep; // keep[k][n] - сколько монет получишь если K = k и осталось n стопок vector >leave; // leave[k][n] - сколько монет оставишь, если сделаешь ход keep[k][n] #else int keep[85][185], leave[85][185]; #endif int n,k; vector mas,sums; void input() { cin>>n; mas.resize(n); sums.resize(n); for (int i=0;i >mas[i]; sums[i] = mas[i]; if (i!=0) sums[i] += sums[i-1]; } cin>>k; #ifdef USE_VECTOR keep = vector >(k, vector (n+1,0)); leave = vector >(k, vector (n+1,0)); #endif } // быстрый подсчет суммы элементов в интервале [f,s] inline int sum(int f, int s) { return sums[s] - sums[f] + mas[f]; } void solve() { // заполняем первую строчку в обоих матрицах // используя принцип чередования ходов keep[0][n-1] = mas[n-1]; for (int j = n-2; j>=0;j--) { keep[0][j] = keep[0][j+2] + mas[j]; leave[0][j] = keep[0][j+1]; } for (int i = 1; i < k; i++) { for (int j = n - 1; j >= 0; j--) { // находим наилучший ход сверху, // т.е находим наилучший ход, если будем уменьшать K int MaxUpKeep = 0; int posUp = 0; for (int p = i - 1; p >= 0; p--) { if (MaxUpKeep < keep[p][j]) { MaxUpKeep = keep[p][j]; posUp = p; } } // находим наилучший ход справа, // т.е. оставляем K без изменений int last = min(j + i, n-1); int MaxRightKeep = sum(j,last) + leave[i][last+1]; if (MaxUpKeep > MaxRightKeep) { keep[i][j] = keep[posUp][j]; leave[i][j] = leave[posUp][j] ; } else { keep[i][j] = MaxRightKeep; leave[i][j] = keep[i][last+1]; } } } } void output() { cout<
 
 
 
 
 
Автор: Администратор
