标签归档：DP

矩阵连乘

发表回复

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <stdio.h> 
#include <string.h> 
#define N 100 
int m[N][N]; //m[i][j]表示从第i个矩阵连乘到第j个矩阵的最小计算次数 
int s[N][N]; //第i个矩阵连乘到第j个矩阵时在何处断开，用于构造最优解 
int p[N];    //表示矩阵i为p[i-1]×p[i] 
 
void MatrixChain(int n) 
{ 
       int i,j,k,t,r; 
       for(i=1;i<=n;i++) 
              m[i][i]=0; 
       for(r=2;r<=n;r++) 
       { 
              for(i=1;i<=n-r+1;i++) 
              { 
                     j=i+r-1; 
                     m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 
                     s[i][j]=i; 
                     for(k=i+1;k<j;k++) 
                     { 
                            t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 
                            if(t<m[i][j]) 
                            { 
                                   m[i][j]=t; 
                                   s[i][j]=k; 
                            } 
                     } 
              } 
       } 
} 
 
void TraceBack(int i,int j) 
{ 
       if(i==j) return; 
       TraceBack(i,s[i][j]); 
       TraceBack(s[i][j]+1,j); 
       printf("Multiply A%d,%d and A%d,%dn",i,s[i][j],s[i][j]+1,j);                                               
 
} 
 
int main() 
 
{ 
       int i,n; 
       memset(m,0,sizeof(m)); 
       scanf("%d",&n); 
       for(i=0;i<=n;i++) 
              scanf("%d",&p[i]); 
       MatrixChain(n); 
       printf("%dn",m[1][n]); 
       TraceBack(1,n); 
       return 0; 
}

邮局问题 vijos1242(和以前的pku上的应该是一样的.)

发表回复

/*
动态规划。
将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为a[1..n]，
状态表示描述为：f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以，f[n,p]即为问题的解，
且状态转移方程和边界条件为：
f[j,1]=w[1,j];
f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j – 1≤k≤i)

其中w[i,j]表示在a[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，
最优解出现在中位数，于是，我们有：
　　w[i,j]=w[i,j]+|a[k]-a[t]| (1<=i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdio.h>
#include <string.h>
#include <math.h>
#define min(a,b) a<b?a:b
int main()
{
int n, m, a[301], f[301][31], i, j , k, w[301][301];                                           
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
    scanf("%d", &a[i]);
for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++)
     f[i][j] = 100000;
 
memset(w, 0, sizeof(w));
for (i = 1; i <= n; i++)
{
    for (j = i; j <= n; j++)
    {
     for (k = i ; k <= j; k++)
      w[i][j] += abs(a[k] - a[(i + j) / 2]);  
    }
}
for (i = 1; i <= n; i++)
    f[i][1] = w[1][i];
for (j = 2; j <= m; j++)
{
    for (i = j; i <= n; i++)
    {
     for (k = j - 1; k < i; k++)
     {
      f[i][j] = min(f[i][j], f[k][j - 1] + w[k + 1][i]);
     }
 
    }
}
 
printf("%d\n", f[n][m]);
return 0;
}