Informatika gyűjtemény

Egy szinttel feljebb mb_robot.cs

2004050607080910

<<  19. óra  >>

<<  Robot  >>

NézetNyomtat

mb_robot.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 3 KB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Robot
{
    class Program
    {
        static int n;
        static TheThing[] things;
        static int[] db1, db2, db3;

        static int[] dp;
        static int[] choice;

        static int result;
        static string backtrace;


        static void Kiir(string file)
        {
            StreamWriter sw = new StreamWriter(file);
            sw.WriteLine(result);
            sw.WriteLine(backtrace);
            sw.Close();
        }

        static void Beolvas(string file)
        {
            string line;
            string[] splittedline;
            StreamReader sr = new StreamReader(file);
            line = sr.ReadLine();
            n = Convert.ToInt32(line);
            things = new TheThing[n];

            for (int i = 0; i < n; i++)
            {
                line = sr.ReadLine();
                splittedline = line.Split(' ');
                things[i] = new TheThing(Convert.ToInt32(splittedline[0]), Convert.ToInt32(splittedline[1]));
            }

            sr.Close();
        }

        static string ChoiceBacktrace(int index)
        {
            if (index < 0) return "";
            int c = choice[index];
            return ChoiceBacktrace(index - c) + " " + Convert.ToString(c);
        }

        static int DP(int lvl)
        {
            if (lvl < 0) return 0;
            if (dp[lvl] != -1) return dp[lvl];
            int[] opt = new int[3];
            opt[0] = lvl >= 0 ? DP(lvl - 1) + db1[lvl] : int.MaxValue / 2;
            opt[1] = lvl - 1 >= 0 ? DP(lvl - 2) + db2[lvl - 1] : int.MaxValue / 2;
            opt[2] = lvl - 2 >= 0 ? DP(lvl - 3) + db3[lvl - 2] : int.MaxValue / 2;

            int min = 0;
            for (int i = 1; i != opt.Length; i++)
                if (opt[i] < opt[min]) min = i;
            choice[lvl] = min + 1;
            dp[lvl] = opt[min];
            return dp[lvl];
        }

        static void DBArrays()
        {
            db1 = new int[n];
            db2 = new int[n - 1];
            db3 = new int[n - 2];

            for (int i = 0; i < db1.Length; i++)
                db1[i] = 2 * (things[i].x + things[i].y);

            for (int i = 0; i < db2.Length; i++)
            {
                int mx, my;
                mx = 0;
                my = 0;
                for (int j = 0; j < 2; j++)
                {
                    if (things[i + j].x > mx) mx = things[i + j].x;
                    if (things[i + j].y > my) my = things[i + j].y;
                }

                db2[i] = 2 * (mx + my);
            }

            for (int i = 0; i < db3.Length; i++)
            {
                int mx, my;
                mx = 0;
                my = 0;
                for (int j = 0; j < 3; j++)
                {
                    if (things[i + j].x > mx) mx = things[i + j].x;
                    if (things[i + j].y > my) my = things[i + j].y;
                }

                db3[i] = 2 * (mx + my);
            }
        }

        static void Munka()
        {
            DBArrays();

            choice = new int[n];
            dp = new int[n];
            for (int i = 0; i < n; i++)
                dp[i] = -1;
            choice[0] = 1;
            dp[0] = db1[0];

            result = DP(n - 1);
            backtrace = ChoiceBacktrace(n - 1).Remove(0, 1);
        }

        static void Main(string[] args)
        {
            Beolvas("robot7.be");
            Munka();
            Kiir("robot.ki");

            Console.ReadKey();
        }
    }

    struct TheThing // :)
    {
        public int x, y;

        public TheThing(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
}
(Vissza)