ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1167. Bicolored Horses

n^2 tle?
Послано Vishal Sharma 12 июн 2014 18:11
#include<bits/stdc++.h>
using namespace std;
int horse[510],i;
long long mem[501][501];
long long count(int index,int left)
{
    if(index==i&&left==0)
    return 0;
    if((index==i&&left>0)||(index<i&&left==0))
    return 1000000;
    if(mem[index][left])
    return mem[index][left];
    int v=0,j=0,k;
    long long mini=1000001;
    for(k=index;k<i;k++)
    {
        if(horse[k])
        v++;
        else
        j++;
        mini=min(mini,v*j+count(k+1,left-1));
    }
    return mem[index][left]=mini;
}
int main()
{
    int j,k,l;
    cin>>i>>j;
    for(k=0;k<i;k++)
    cin>>horse[k];
    cout<<count(0,j)<<endl;
    return 0;
}