花店橱窗布置

#include<iostream>

#include<cstring>

using namespace std;

const int INF = -5000;

const int MAXC = 100;

const int MAXM = 100;

int V[MAXC+1][MAXM+1];

int B1[MAXC+1][MAXM+1];

int B2[MAXC+1][MAXM+1];

int B3[MAXC+1][MAXM+1];

int pre[MAXM+1];

int cur[MAXM+1];

int F1[MAXM+1];

int X[MAXC+1];

int BX[MAXC+1];

int bestValue = INF;

int C[MAXC+1][MAXM+1];

int Best_1(int n, int m);

int Best_2(int n, int m);

int Best_3(int n, int m);

void Show(int i, int j);

int Show_2(int n, int m);

void DFS(int n, int i, int j);

int MDFS(int i, int j);

void Show_3(int n, int m);

int main()

{

int n, m;

cin >> n >> m;

for (int i=1; i<=n; i++)

{

for (int j=1; j<=m; j++)

{

cin >> V[i][j];

}

}

cout << Best_1(n, m) << endl;

Show(n, m);

cout << Show_2(n, m) << endl;

cout << Best_2(n, m) << endl;

cout << Best_3(n, m) << endl;

DFS(n, n, m);

cout << bestValue << endl;

for (int i=1; i<=n; i++)

{

cout << BX[i] << " ";

}

cout << endl;

for (int i=1; i<=MAXC; i++)

{

for (int j=1; j<=MAXM; j++)

{

B2[i][j] = INF;

}

}

cout << MDFS(n, m) << endl;

Show_3(n, m);

return 0;

}

int Best_1(int n, int m)

{

for (int i=1; i<=n; i++)

{

for (int j=i; j<=m-n+i; j++)

{

int bestP = INF;

for (int k=i; k<=j; k++)

{

if (bestP < B1[i-1][k-1] + V[i][k])

bestP = B1[i-1][k-1] + V[i][k];

}

B1[i][j] = bestP;

}

}

return B1[n][m];

}

void Show(int i, int j)

{

if (i == 0 || j == 0)

return;

for (int k=j; k>=i; k--)

{

if (B1[i][j] == B1[i-1][k-1] + V[i][k])

{

Show(i-1, k-1);

cout << k << " ";

break;

}

}

}

int Show_2(int n, int m)

{

for (int i=n,j=m; i>0; i--)

{

for (int k=i; k<=j; k++)

{

if (B1[i][j] == B1[i-1][k-1] + V[i][k])

{

X[i] = k;

j = k - 1;

break;

}

}

}

int s = 0;

for (int i=1; i<=n; i++)

{

cout << X[i] << " ";

s += V[i][X[i]];

}

cout << endl;

return s;

}

int Best_2(int n, int m)

{

for (int i=1; i<=n; i++)

{

for (int j=i; j<=m-n+i; j++)

{

int bestP = INF;

for (int k=i; k<=j; k++)

{

if (bestP < pre[k-1] + V[i][k])

bestP = pre[k-1] + V[i][k];

}

cur[j] = bestP;

}

for (int j=i; j<=m-n+i; j++)

{

pre[j] = cur[j];

}

}

return pre[m];

}

int Best_3(int n, int m)

{

for (int i=1; i<=n; i++)

{

for (int j=m-n+i; j>=i; j--)

{

int bestP = INF;

for (int k=i; k<=j; k++)

{

if (bestP < F1[k-1] + V[i][k])

bestP = F1[k-1] + V[i][k];

}

F1[j] = bestP;

}

}

return F1[m];

}

void DFS(int n, int i, int j)

{

if (i==0 || j==0)

{

int s = 0;

for (int k=1; k<=n; k++)

{

s += V[k][X[k]];

}

if (bestValue < s)

{

bestValue = s;

for (int k=1; k<=n; k++)

{

BX[k] = X[k];

}

}

return;

}

for (int k=i; k<=j; k++)

{

X[i] == k;

DFS(n, i-1, k-1);

}

}

int MDFS(int i, int j)

{

if (B2[i][j] != INF)

return B2[i][j];

if (i==0 || j==0)

return 0;

int bestP = INF;

for (int k=i; k<=j; k++)

{

if (bestP < MDFS(i-1, k-1) + V[i][k])

bestP = MDFS(i-1, k-1) + V[i][k];

}

return B2[i][j] = bestP;

}

void Show_3(int n, int m)

{

int bestP, pos;

for (int i=1; i<=n; i++)

{

for (int j=i; j<=m-n+i; j++)

{

bestP = INF;

for (int k=i-1; k<j; k++)

{

if (bestP < B3[i-1][k] + V[i][j])

{

bestP = B3[i-1][k] + V[i][j];

C[i][j] = k;

}

}

B3[i][j] = bestP;

}

}

bestP = INF;

for (int j=n; j<=m; j++)

{

if (bestP < B3[n][j])

{

bestP = B3[n][j];

pos = j;

}

}

cout << bestP << endl;

for (int i=n; i>0; i--)

{

X[i] = pos;

pos = C[i][pos];

}

for (int i=1; i<=n; i++)

{

cout << X[i] << " ";

}

cout << endl;

}