mercredi 6 janvier 2016

cost of cutting a plank

I know that this question has been asked but i cant understand the problem in my code. I know that we have to use cost in desending order for minimum cost and i did same but still gives wrong output.

A board composed of m×n wooden squares and asks him to find the minimum cost of breaking the board back down into individual 1×1 pieces. To break the board down, Bob must make cuts along its horizontal and vertical lines.

To reduce the board to squares, xn−1 vertical cuts must be made at locations x1,x2,…,xn−2,xn−1 and ym−1 horizontal cuts must be made at locations y1,y2,…,ym−2,ym−1. Each cut along some xi (or yj) has a cost, cxi (or cyj). If a cut of cost c passes through n already-cut segments, the total cost of the cut is n×c.

The cost of cutting the whole board down into 1×1 squares is the sum of the cost of each successive cut. Recall that the cost of a cut is multiplied by the number of already-cut segments it crosses through, so each cut is increasingly expensive.

Input Format

The first line contains a single integer, T, denoting the number of test cases. The subsequent 3T lines describe each test case in 3 lines.

For each test case, the first line has two positive space-separated integers, m and n, detailing the respective height (y) and width (x) of the board. The second line has m−1 space-separated integers listing the cost, cyj, of cutting a segment of the board at each respective location from y1,y2,…,ym−2,ym−1. The third line has n−1 space-separated integers listing the cost, cxi, of cutting a segment of the board at each respective location from x1,x2,…,xn−2,xn−1.

Note: If we were to superimpose the m×n board on a 2D graph, x0, xn, y0, and yn would all be edges of the board and thus not valid cut lines.

Constraints 1≤T≤20 2≤m,n≤1000000 ,0≤cxi,cyj≤1000000000

Output Format

For each of the T test cases, find the minimum cost (MinimumCost) of cutting the board into 1×1 squares and print the value of MinimumCost % (1000000000+7).

#include <iostream>
#include <limits>
using namespace std;

int main() {
    int t,ch=0;
    long int pos,m,n,h=1,l=1;
    long long int cost=0,*x,*y,temp;
    cin>>t;
    while(t>0)
    {cin>>m>>n;
    x = new long long int[n-1];
    y = new long long int[m-1];
    for (long i=0;i<m-1;i++)
        cin>>y[i];
    for(long i=0;i<n-1;i++)
        cin>>x[i];
    h=1;
    l=1;
    while((h!=m)|(l!=n))
    {ch=0;
    temp=0;
    for (long i=0;i<m-1;i++)
        if (temp<y[i])
            {temp=y[i];
            pos=i;
            }
    for(long i=0;i<n-1;i++)
        if (temp<x[i])
        {temp=x[i];
        pos=i;
        ch=1;
        }
    cost=cost+temp*(ch==0?l:h);
    if (ch==0)
            {y[pos]=-1;
            h++;}
        else
            {x[pos]=-1;
            l++;
            }

    }
    cout<<cost%1000000007;
    t--;

    }
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire