2020-01-14
92
suits = ['H', 'S', 'C', 'D']
values = ["2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"]
def get_value(suit, val):
return suits.index(suit) * 13 + values.index(val);
n = int(input())
a = []
for i in range(n):
suit, val = input().split()
a.append(get_value(suit, val))
s = sum(a)
dp1 = []
for i in range(n):
dp1.append([0] * n)
for left in range(n-1,-1,-1):
for right in range(left, n):
if left == right:
dp1[left][right] = a[left]
elif right - left == 1:
dp1[left][right] = max(a[left], a[right])
else:
dp1[left][right] = max(
a[left] + min(dp1[left+2][right], dp1[left+1][right-1]),
a[right] + min(dp1[left+1][right-1], dp1[left][right-2]),
)
t = dp1[0][n-1]
if 2 * t > s:
print('FYODOR')
elif 2 * t == s:
print('DRAW')
else:
print('DJON')
Решение на языке GNU C++11
#include <bits/stdc++.h>
using namespace std;
char suits[] = {'H', 'S', 'C', 'D'};
string values[] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
int dp[101][101] = {};
int get_value(char suit, string val)
{
int i = 0, j = 0;
while (suit!= suits[i]) ++i;
while (val!= values[j]) ++j;
return i * 13 + j;
}
string get_card(int value)
{
int i = value / 13;
int j = value % 13;
return string(1, suits[i]) + " " + values[j];
}
int f(int left, int right, const vector<int> & deck)
{
if (!dp[left][right])
|
|
|
{
if (left > right) dp[left][right] = 0;
else if (left == right) dp[left][right] = deck[left];
else if (right - left == 1) dp[left][right] = max(deck[left], deck[right]);
else
{
dp[left][right] = max(
deck[left] + min(f(left+2, right, deck), f(left+1, right-1, deck)),
deck[right] + min(f(left+1, right-1, deck), f(left, right-2, deck))
);
}
}
return dp[left][right];
}
void solve(const vector<int> & deck)
{
int fedor = f(0, int(deck.size())-1, deck);
int s = 0;
for(int i=0; i<int(deck.size()); ++i) s += deck[i];
if (2 * fedor > s)
cout << "FYODOR";
else if (2 * fedor == s)
cout << "DRAW";
else
cout << "DJON";
}
int main() {
vector<int> deck;
int n;
cin >> n;
while(n > 0)
{
char suit;
string val;
cin >> suit >> val;
deck.push_back(get_value(suit, val));
n--;
}
solve(deck);
return 0;
}
F. Максимальный deck
Для решения задачи необходимо реализовать топологическую сортировку – известный алгоритм на графах, реализуемый с помощью поиска в глубину (подробнее о нем можно прочитать, например на сайте https://e-maxx.ru/algo/). Также, можно заметить, что задачу следует решать в целых числах, для чего необходимо умножить все числа подаваемые при вводе данных на 100. Для хранения номеров городов лучше всего использовать ассоциативный массив (словарь: dict в Python, map в C++), который позволит быстро (за O(log n)) получать информацию о номерах городов по их названию.
Заметим, что топологическую сортировку нужно запускать только для вершин, которые являются обязательными для посещения, а также для вершин, которые должны быть посещены перед тем, как посетить вершины обязательные для посещения. Удобно обе эти категории вершин отметить, как обязательные для посещения (required).
Далее приводится решение на языке C++
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<string> cities;
map<string, int> city_id;
vector<int> prices;
vector<bool> required;
|
|
|
vector< vector<int> > required_list;
vector<int> city_order;
vector<bool> used;
void find_required(int city)
{
required[city] = true;
for(auto rtown: required_list[city])
find_required(rtown);
}
void top_sort(int city)
{
if (used[city]) return;
used[city] = true;
for(auto town: required_list[city])
top_sort(town);
city_order.push_back(city);
}
void solve()
{
// check all required cities
for(int i=0; i<n; ++i) if (required[i]) find_required(i);
// top sort for nodes
used.resize(n, false);
long long price = 0;
for(int i=0; i<n; ++i)
if (required[i])
{
price += 1LL * prices[i];
top_sort(i);
}
// show results
printf("%d\n", city_order.size());
for(auto id: city_order)
printf("%s\n", cities[id].c_str());
printf("%lld.%02d", price / 100, price % 100);
}
void read()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cities.resize(n);
prices.resize(n);
required.resize(n, false);
for(int i=0; i<n; ++i)
{
string town;
double price;
int mark;
cin >> town >> price >> mark;
cities[i] = town;
city_id[town] = i;
prices[i] = round(price * 100LL);
required[i] = mark;
}
cin >> m;
assert(m <= 500);
required_list.resize(n);
for(int i=0; i<m; ++i)
{
string town1, town2;
cin >> town1 >> town2;
required_list[ city_id[town2] ].push_back(city_id[town1]);
}
}
int main()
{
read();
solve();
return 0;
}
Еще одно решение на C++, которое также получает полный балл и вместо разных массивов для хранения информации использует структуру данных.
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
using namespace std;
struct {
string town;
double price;
bool req;
bool visited;
int order;
} v[250];
int order[250], ord;
multimap<int, int> depend;
map<string, int> townNums;
long double sum;
void recSum(int i) {
if (v[i].visited)
return;
v[i].visited = true;
auto prev = depend.equal_range(i);
for (auto j = prev.first; j!= prev.second; j++)
recSum((*j).second);
sum += v[i].price;
order[++ord] = i;
}
int main() {
int n, m;
string s;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i].town >> v[i].price >> v[i].req;
townNums[v[i].town] = i;
}
cin >> m;
pair<int, int> dep;
for (int i = 1; i <= m; ++i) {
cin >> s;
dep.second = townNums[s];
cin >> s;
dep.first = townNums[s];
depend.insert(dep);
}
for (int i = 1; i <= n; ++i) {
if (v[i].req)
recSum(i);
}
cout << ord << endl;
for (int i = 1; i <= ord; ++i)
cout << v[order[i]].town << endl;
cout << fixed << setprecision(2) << sum << endl;
return 0;
}
