Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.11.2010, 22:51
Новичок

Отправить личное сообщение для хус++ Посмотреть профиль Найти все сообщения от хус++
 
Регистрация: 09.11.2010
Сообщений: 7

задача агент на дп
здравтсвуйте дорогие форумчане, есть следующая хитрожопая задача
Агент
(Время: 1 сек. Память: 16 Мб Сложность: 34%)

Агент Джеймс Бонд пошел на пенсию, но неугомонный характер требовал новых впечатлений. Поэтому Джеймс Бонд с удовольствием согласился провести мастер-класс в некоторых группах школы «Молодого агента». Тема одного из занятий – работа агента с напарником. В таком опасном деле, как разведка, важно иметь очень надёжного напарника, поэтому напарниками могут стать только агенты, которые максимально близки по возрасту (т.е. два агента не могут стать напарниками, если в группе существует третий агент, который старше одного и младше другого).

Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть 2 напарника – один младше, и один старше него, но эти двое не считаются напарниками между собой). Очевидно, что группа из 4 и более агентов может поделиться несколькими способами.

После нескольких занятий Бонд узнал способности групп, обучающихся в школе «Молодого агента», и оценил риск раскрытия каждого агента в отдельности. Но специфика работы с напарником такова, что в паре риску подвергается только старший из двух агентов, поэтому группу надо распределить так, чтобы суммарный риск был минимален.

Входные данные

В первой строке входного файла INPUT.TXT находится одно целое число N – количество агентов в группе (2 <= N <= 10000). Во второй строке находятся N пар целых положительных чисел, разделенных пробелом. Первое число в паре – это возраст агента (в днях) из диапазона [5000, 16000], второе – риск раскрытия агента, число в диапазоне [1, 1000]. Известно, что в любой группе все агенты разного возраста.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число – минимальное значение суммарного риска раскрытия группы.
INPUT.TXT
3
6000 2 5500 3 5000 4
OUTPUT.TXT
5
INPUT.TXT
5
5005 1 5004 2 5003 3 5002 4 5001 5
OUTPUT.TXT
7
так же есть тест где 10000 агентов. возраст идет по порядку от 5000 до 14999, раскрытие тоже порядку от 1 до 1000 десять раз.
ответ: 2500502
возраст у всех разный!
  #2  
Старый 09.11.2010, 23:05
гость

 
Сообщений: n/a

Ну и в чем проблема? По моему тривиально. Отсортировать и дп за O(n).
  #3  
Старый 10.11.2010, 12:48
Новичок

Отправить личное сообщение для хус++ Посмотреть профиль Найти все сообщения от хус++
 
Регистрация: 09.11.2010
Сообщений: 7

отсортировал по возрасту и посчитал за О(n)
Код:
#include <string.h>
#include <iostream>
#include <stdio.h>
using namespace std;
        int min(int a,int b)
        {
        if(a<b)return a;
        return b;
        }
        int i, n, j;
		int r[11000], v[11000], b[11000];		
        void ssv()
        {
     int xr, xv;        
     for(int i=1;i<n;i++)
    {
     xv=v[i];
     xr=r[i];
     int j=i-1;
     while(xv<v[j] && j>=0)
     {
     v[j+1]=v[j];
     r[j+1]=r[j];
     j--;
     }
     v[j+1]=xv;
     r[j+1]=xr;
    }
        }
        int main(void)
        {
        freopen("INPUT.TXT","r",stdin);
        freopen("OUTPUT.TXT","w",stdout);
        cin >> n;
        for(i=0;i<n;i++)
        {
        cin >> v[i];
        cin >> r[i];
        }
		 ssv();
        b[0]=0;
		b[1]=0;
        for(i=2;i<=n+1;i++)
        {
        b[i]=min(b[i-1],b[i-2])+r[i-2];
        }	
        cout << b[n+1];
        return 0;
        }
Wrong answer 12
буду очень рад если вы укажете что не так

Последний раз редактировалось хус++, 10.11.2010 в 20:11.
  #4  
Старый 10.11.2010, 13:11
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

хус++,
используйте тэг CODE (# в списке быстрых тэгов при создании сообщения)
  #5  
Старый 10.11.2010, 20:12
Новичок

Отправить личное сообщение для хус++ Посмотреть профиль Найти все сообщения от хус++
 
Регистрация: 09.11.2010
Сообщений: 7

MBo,
спасибо, больше так тупить не буду
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра