Pernyataan masalah:

Permutasi elemen-N adalah barisan elemen-N dari bilangan yang berbeda dari himpunan {1, 2, ...,n}. Misalnya barisan 2,1,4,5,3 adalah permutasi 5 elemen. P adalah permutasi elemen-N. Tugas Anda adalah mengurutkan P dalam urutan menaik. Tapi karena sangat sederhana, saya punya aturan baru untuk Anda. Anda memiliki dua barisan P dan Q. P adalah permutasi elemen-N dan Q awalnya kosong dan dibentuk dengan mengurutkan P (yaitu akhirnya Q = 1, 2, 3,... , N). Anda harus menerapkan N langkah untuk mengurutkan P. Pada langkah ke-i, P memiliki elemen sisa N-i+1, Q memiliki elemen i-1 dan Anda harus memilih beberapa elemen ke-x (dari N-i+ 1 elemen yang tersedia) dari P dan letakkan di kiri atau kanan Q. Biaya langkah ini sama dengan x * i. Biaya total adalah jumlah biaya dari setiap langkah. Setelah N langkah, Q harus barisan menaik. Tugas Anda adalah meminimalkan total biaya.

Memasukkan

Baris pertama dari file input adalah T (T 10), jumlah kasus uji. Kemudian deskripsi kasus uji T mengikuti. Deskripsi setiap test case terdiri dari dua baris. Baris pertama berisi satu bilangan bulat N (1 N 1000). Baris kedua berisi N bilangan bulat berbeda dari himpunan {1, 2, .., N}, permutasi elemen-N P.

Keluaran

Untuk setiap kasus uji, program Anda harus menulis satu baris, berisi satu bilangan bulat - total biaya penyortiran minimum.

Masukan: 1 4 4 1 3 2

Keluaran: 15

Solusi saya:

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int sz;
int n[1001];
map<int,int>pos;
int solve(int i,int a,int b){
if(a==-1&&b==sz) //if all the elements have been moved 
    return 0;
if(i>sz)
    return INT_MAX;
    int ret = INT_MAX;
    if(a>=0) //select the element from left
        ret = min(ret,solve(i+1,a-1,b)+((i+1)*pos[n[a]]));
    if(b<sz) //select the element from right
        ret = min(ret,solve(i+1,a,b+1)+((i+1)*pos[n[b]]));
return ret;
}

int main()
{
   int t;
   cin>>t;
   while(t--){
        cin>>sz;
   for(int i=0;i<sz;i++){
    int x;
    cin>>x;
    n[i] = x; //value
    pos[x] = i+1; //position of elements of array before sorting
   }
   sort(n,n+sz); //sorting the array
   int ret = INT_MAX;
   for(int i=0;i<sz;i++)  
     ret= min(ret,solve(0,i,i+1));
             cout << ret << endl;

        }
    return 0;
}

Ini mengembalikan jawaban yang salah. Apa yang salah dengan pendekatan saya? Bagaimana ini bisa diperbaiki?

-1
Saksham 15 Juni 2016, 17:49

1 menjawab

Jawaban Terbaik

Satu masalah adalah Anda menghitung biaya berdasarkan pos[n[a]].

Pos[n[a]] mengembalikan posisi dalam larik asli, tetapi biayanya harus didasarkan pada posisi dalam larik P saat ini (yaitu dengan beberapa elemen dipindahkan ke Q).

Misalnya, jika P awalnya {4,1,2} maka posisi 2 adalah x==3, tetapi setelah P dikurangi menjadi {1,2}, maka posisi 2 adalah x==2.

0
Peter de Rivaz 15 Juni 2016, 18:35
Bagaimana saya bisa memperbaiki ini?
 – 
Saksham
15 Juni 2016, 18:50