![:o](./images/smilies/icon_eek.gif)
THX!
Moderator: Board moderators
Bad news: No, I can't paste or post my code herebnbolo wrote:could you please paste your code out , or give your algorithm in pseudocode?
THX!
Code: Select all
Accepted, NO SPOILING!
Code: Select all
for i := 0 to 2000 do
for j := 0 to 2000 do
dp[i, j] := 99999;
I 've got AC, thank you!!! [I have declared too large array sizeangga888 wrote:You only need to initialize the variable as needed. No need to always perform 2000*2000 loop as above.Code: Select all
for i := 0 to 2000 do for j := 0 to 2000 do dp[i, j] := 99999;
Code: Select all
// Headers, etc...
#define in cin
using namespace std;
vector<int> CutSpots;
int length, cuts;
vector< vector<int> > memo;
int MV = 1<<15;
int BestWay(int a, int b)
{
if(memo[a][b] != -1)
return memo[a][b];
if(b-a == 1)
return memo[a][b] = 0;
int minv = MV;
for(int i = a+1; i < b; ++i)
{
//cut here
minv = min(minv, (CutSpots[i]-CutSpots[a]) + (CutSpots[b]-CutSpots[i])
+ BestWay(a,i) + BestWay(i, b) );
}
return memo[a][b] = minv;
}
int main()
{
//ifstream in("in.txt");
while(1)
{
in >> length;
if(length == 0)
break;
in >> cuts;
CutSpots = vector<int>(cuts);
CutSpots.push_back(0);
//given in increasing order
for(int i = 0; i < cuts; ++i)
in >> CutSpots[i+1];
CutSpots.push_back(length);
memo = vector< vector<int> >(cuts+2, vector<int>(cuts+2,-1));
cout << "The minimum cutting is " << BestWay(0, cuts+1) << "." << endl;
}
return 0;
}
Code: Select all
import java.io.*;
import java.util.*;
class p10003
{
public static void main(String args[]) throws IOException
{
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(stdin.readLine());
while (m != 0)
{
int n = Integer.parseInt(stdin.readLine());
String[] sp = stdin.readLine().split(" ");
a = new int[n];
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(sp[i]);
d = new int[m + 1][m + 1];
for (int i = 0; i <= m; i++)
for (int j = 0; j <= m; j++) d[i][j] = -1;
System.out.println("The minimum cutting is " + C(0, m) + ".");
m = Integer.parseInt(stdin.readLine());
}
}
static int[][] d;
static int[] a;
static int C(int left, int right)
{
if (d[left][right] != -1) return d[left][right];
int ret = 10000;
for (int i = 0; i < a.length; i++)
if (a[i] > left && a[i] < right)
{
ret = Math.min(ret, C(left, a[i]) + C(a[i], right));
}
if (ret == 10000) ret = 0;
else ret += right - left;
d[left][right] = ret;
return ret;
}
}
Code: Select all
//removed after AC