转载请注明~ 如果有理解不到位或错误的情况，劳烦大神指正，一定感激不尽！
题目来源：CCF201612-4 压缩编码
题目的意思是：
1. 顺序给定文字中n个单词出现的频率（次数）；
2. 对这n个单词进行编码，要求按照字典序；
3. 在满足字典序的基础上使文字经过编码后的长度最小；
样例输入：
5
1 3 4 2 5
样例输出：
34
思路：条件反射的想到了哈夫曼编码，但由题可知这是不可行的，因为没有保证对单词以字典序编码。在其他博客中发现了用动态规化的方法来解决这个问题：http://blog.csdn.net/zmx19951103/article/details/61200633 。 有一点疑惑的就是，当n为1时，即只有一个单词（编码为0或1），文字经过编码后的最小长度应该就是它的频率w1；但是石子问题中，只有一堆石子的情况下，合并花费为0。在n>1情况下感觉倒是和石子合并是相同的。在此稍加整理。
子问题：用dp[i][j]表示第i到第j个单词按字典序最小编码的长度。在组合子问题解的过程中，便保持了按字典序编码的要求。如下图1所示。
当 i = j 时，dp[i][j]是一个叶子结点，它的最小编码就是第i个字母的频率wi：dp[i][j] = wi ( i = j );
当 i < j 时，dp[i][j]是一个分支结点，表示从第i个字母到第j个字母由对应频率组成的文本的最小编码长度，添加分支结点表示树加深了一层（见下图），因此:
dp[i][j] = min( dp[i][j], dp[i][k] + dp[k+1][j] + cost ) ( i <= k < j ) ;
当dp[i][k]或dp[k+1][j]为叶子结点时，其所在分支深度并没有增加，其对应字母的编码长度也没有增加；当dp[i][k]或dp[k+1][j]为分支结点时，其深度加1，需要将第i到k个字母的频率之各或第k+1到j个字母的频率之和加入到cost中（图2）。
图1
图2（第二行公式中括号里为cost）
代码如下：
#include <iostream> #include <algorithm> #define MAX 0x7fffffff using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int frequence[1001]; // 满足最大的n int sumOfFre[1001]; int dp[1001][1001]; // should output dp[1][n] int main(int argc, char** argv) { //读取数据 int n; cin >> n; sumOfFre[0] = 0; frequence[0] = 0; for( int i = 1; i <= n; i++ ) { cin >> frequence[i]; sumOfFre[i] = sumOfFre[i-1] + frequence[i]; dp[i][i] = frequence[i]; //下标从 1 ~ n //dp[i][i] = 0; //下标从 1 ~ n } for( int step = 1; step < n; step++ ) // step=1,得到 dp[1][2],dp[2][3],dp[i][i+step], // step=2,得到 dp[1][3],dp[2][4],dp[i][i+step], // ...... // step=n-2,1 <= i < 3 得到 dp[1][n-1],dp[2,n] // step=n-1,1 <= i < 2 得到 dp[1][n] { for( int i = 1; i < n-step+1; i++ ) { int j = i + step; dp[i][j] = MAX; for( int k = i; k < j; k++ ) { if( k != i && (k+1) != j ) { dp[i][j] = min( dp[i][k] + dp[k+1][j] + sumOfFre[j] - sumOfFre[i-1], dp[i][j] ); // cout << "---1 i: " << i << " k: " << k << " j: " << j << " dp[i][j]: " << dp[i][j] << endl; } else if ( k == i && (k+1) != j ) { dp[i][j] = min( dp[i][k] + dp[k+1][j] + sumOfFre[j] - sumOfFre[k], dp[i][j] ); // cout << "---2 i: " << i << " k: " << k << " j: " << j << " dp[i][j]: " << dp[i][j] << endl; } else if ( k != i && (k+1) == j ) { dp[i][j] = min( dp[i][k] + dp[k+1][j] + sumOfFre[k] - sumOfFre[i-1], dp[i][j] ); // cout << "---3 i: " << i << " k: " << k << " j: " << j << " dp[i][j]: " << dp[i][j] << endl; } else if ( k == i && (k+1) == j ) { dp[i][j] = min( dp[i][k] + dp[k+1][j], dp[i][j] ); // cout << "---4 i: " << i << " k: " << k << " j: " << j << " dp[i][j]: " << dp[i][j] << endl; } //dp[i][j] = min( dp[i][k] + dp[k+1][j] , dp[i][j] ); } } } cout << dp[1][n] << endl; return 0; }
-----------------------------------------------------------------------------------------------------------------------------------------------
题目来源：一道笔试题 Wireless Routers http://blog.csdn.net/qiangli_strong/article/details/52749860
题目的意思是：
1. N个房间，N-1个门；
2. 每个门连接两个房间，每个房间至少1个门，至多3个门；
3. 将M个路由器放入N个房间，每个路由器只能覆盖当前房间与相邻房间；
4. S[i]表示如果第i个屋子有路由器的满意度；
5. 求一种方案最大化所有屋子的满意度之和。
样例输入：
5 1 // 5个房间，1个路由器
1 2 3 4 5 // 5个房间的满意度
2 1 // 2号与1号房间有一扇门
3 2
4 2
5 3
样例输出：
10
思路：totalPoint[i][j]表示在前j个房间中放置i个路由器从而达到了最高的满意度总和，有两种情况，
1. 第j个房间不放路由器，即在前j-1个房间中放了i个路由器；
2. 第j个房间放路由器，即在前j-1个房间中放了i-1个路由器；
那么 totalPoint[i][j] = max( totalPoint[i][j-1], totalPoint[i-1][j-1] + gain )，其中gain为第j个房间放路由器所带来的满意度的提升。（totalPoint[i][0]=totalPoint[0][j]===0)
代码如下：
public class WR { public static int findMaxPoint( int N, int M, int[] roomPoint, int[][] doors ) { int[][] totalPoint = new int[ M+1 ][ N+1 ]; Set< Integer >[][] roomWiFi = new HashSet[M+1][N+1]; for( int i = 0; i <= M; i++ ) //M路由器数 { for( int j = 0; j <= N; j++ ) //N房间数 { roomWiFi[i][j] = new HashSet< Integer >(); //roomWiFi[i][j]表示前j个房间放入了i个路由器的最高满意度方案中，都有哪些房间已经被WiFi覆盖。 } } for( int m = 1; m <= M; m++ ) //M路由器数 { // totalPoint[ m ][ n ] 表示前n个房间放入了m个路由器的最优满意度分数 //求出当第n个房间放入路由器后(前n-1个房间放入了m-1个路由器）， // 比第n个房间不放路由器(前n-1个房间放入了m-1个路由器），所增加的满意度分数 for( int n = m; n <= N; n++ ) { int gain = 0; if( roomWiFi[m-1][n-1].isEmpty() ) { for( int i = 1; i <= N; i++ ) { if( doors[n][i] == 1 ) { gain += roomPoint[i]; } } } else { for( int hasWiFi : roomWiFi[m-1][n-1] ) { for( int i = 1; i <= N; i++ ) { if( (doors[hasWiFi][i] == 0) && (doors[n][i] == 1 ) ) { gain += roomPoint[i]; } } } } if( totalPoint[ m ][ n-1 ] < totalPoint[ m-1 ][n-1] + gain ) { totalPoint[ m ][ n ] = totalPoint[ m-1 ][n-1] + gain; roomWiFi[m][n].addAll( roomWiFi[m-1][n-1] ); roomWiFi[m][n].add( n ); } else { totalPoint[ m ][ n ] = totalPoint[ m ][ n-1 ] ; roomWiFi[m ][n ].addAll( roomWiFi[m] [n-1] ); } } } // System.out.println( totalPoint[M][N] ); return totalPoint[M][N]; } public static void main(String[] args) { int M, N; Scanner sc = new Scanner( System.in ); String line = sc.nextLine(); N = Integer.parseInt( line.split(" ")[0] ); M = Integer.parseInt( line.split(" ")[1] ); int[] roomPoint = new int[N+1]; int[][] doors = new int[ N+1 ][N+1]; line = sc.nextLine(); for( int i = 1; i <= N; i++ ) { int a = Integer.parseInt( line.split(" ")[i-1] ); roomPoint[i] = a; } for( int i = 1; i <= N-1; i++ ) { line = sc.nextLine(); int a = Integer.parseInt( line.split(" ")[0] ); int b = Integer.parseInt( line.split(" ")[1] ); doors[a][b] = 1; doors[b][a] = 1; doors[a][a] = 1; doors[b][b] = 1; } int s = findMaxPoint( N, M, roomPoint, doors ); System.out.println( s ); } }
--------------------------------------------------------------------------------------------------------------------------------------------------------------
题目来源：作业 凸多边形最优三角形划分 http://www.cnblogs.com/Jason-Damon/p/3298172.html
代码如下：
cpt.c: #include <stdio.h> #include "cpt.h" int main() { int i,j; double a_k=0.0; time = 0; read_from_file( "test_10.txt"); init_weight(); set_array_zero( 0, vertex_num, min_w ); a_k = min_weight( 1, vertex_num-1 ); printf( "Min cost: %lf ", a_k ); print_out( 1, vertex_num-1, s ); read_from_file( "test_30.txt"); init_weight(); set_array_zero( 0, vertex_num, min_w ); //a_k = min_weight( 1, vertex_num-1 ); a_k = min_weight_recursion( 1, vertex_num-1 ); printf( "Min cost: %lf ", a_k ); print_out( 1, vertex_num-1, s ); getchar(); return 0; } func.c: #include <stdio.h> #include <stdlib.h> //atof #include <math.h> #include "cpt.h" void set_array_zero( int i, int j, double a[][VERTEX_MAXNUM]) { int m, n; for( m = i; m < j; m++ ) { for( n = i; n < j; n++ ) { a[m][n] = 0.0; } } } void read_from_file( char *file ) { char str[100]; char *p; int i; FILE* f = fopen( file, "r" ); if( f == NULL ) { printf( "Open file error " ); exit( 1 ); } /*文件示例：
n=30
(40.000,80.000)
(47.495,79.291)
(57.031,76.193)
(63.511,72.361)
(73.773,61.433)
...*/
//文件第一行 顶点数 fgets( str, 100, f ); p = strchr( str, '='); vertex_num = atoi( p+1 ); //sscanf( str, "n=%d", &vertex_num ); //fscanf( f, "n=%d", &vertex_num ); printf( "vertex_num:%d ", vertex_num); /* fgets( str, 100, f ); printf( "%s", str); fgets( str, 100, f ); printf( "%s", str); */ //坐标，初始化coor数组 for( i = 0; (i < vertex_num) && (fgets( str, 100, f )!=NULL); i++ ) { p = strtok( str, "(, ) " ); while( p == NULL ) { fgets( str, 100, f ); p = strtok( str, "(, ) " ); } //printf( "%s,,", p); coor[i].x = atof( p ); p = strtok( NULL, "( , )]r " ); //printf( "%s ", p); coor[i].y = atof( p ); //printf("coor[%d]x: %f,coor[%d]y: %f ", i,coor[i].x,i,coor[i].y); } fclose( f ); } //计算两点距离 double calculate_distance( double x1, double y1, double x2, double y2) { return sqrt( ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ) ); } //初始化邻接矩阵 void init_weight() { int i, j; for( i = 0; i < vertex_num; i++ ) { for( j = i; j < vertex_num; j++) { weight[i][j] = calculate_distance( coor[i].x, coor[i].y, coor[j].x, coor[j].y ); //printf( "%f ", weight[i][j]); } //printf( " "); } } double min_weight( int i, int j ) { set_array_zero( 0, vertex_num, min_w ); int r, begin, end, k; double min = 1000000.0, ret; for( r = 2; r < vertex_num; r++ ) //r为子问题规模 { for( begin = 1; begin < vertex_num-r+1; begin++ ) { end = begin + r - 1; min = 1000000.0; for( k = begin; k < end; k++ ) {
// min_w[i][j]代表从顶点i-1到j的最优三角划分后的权值总和 ret = min_w[begin][k] + min_w[k+1][end] + weight[begin-1][k] + weight[k][end] + weight[begin-1][end]; if( ret < min ) { min = ret; s[begin][end] = k; } } min_w[begin][end] = min; } } return min_w[1][vertex_num-1]; } //递归实现 double min_weight_recursion( int i, int j ) { set_array_zero( 0, vertex_num, min_w ); int k, flag; double ret = 10000000.0; double a, f1, f2; if( i == j ) //i-1, j 两个点 { //printf( "1 "); return 0.0; } for( k = i; k < j; k++ ) { //判断已经存储好的值 if( min_w[i][k] != 0.0 ) f1 = min_w[i][k]; else f1 = min_weight( i, k ); if( min_w[k+1][j] != 0.0 ) f2 = min_w[k+1][j]; else f2 = min_weight( k+1, j ); //a = min_weight( i, k ) + min_weight( k+1, j ) + weight[i-1][k] + weight[k][j] + weight[i-1][j]; a = f1 + f2 + weight[i-1][k] + weight[k][j] + weight[i-1][j]; if( ret > a ) { ret = a; flag = k; } } s[i][j] = flag; min_w[i][j] = ret; //printf( "~~~~~~~%d~ %d~ %d~ %lf~ time:%d ", i-1, flag, j, ret, time++); return ret; } void print_out( int i, int j, int s[][VERTEX_MAXNUM] ) { if( i == j) { return; } int k = s[i][j]; printf( "V%d V%d V%d ", i-1, k, j ); print_out( i, k, s); print_out( k+1, j, s ); } cpt.h: #ifndef _CPT_H #define _CPT_H #define VERTEX_MAXNUM 100 typedef struct coordinate { double x; double y; } Coordinate; // 顶点坐标 Coordinate coor[ VERTEX_MAXNUM ]; //邻接矩阵 上三角 double weight[ VERTEX_MAXNUM ][ VERTEX_MAXNUM ]; //实际顶点数 int vertex_num; //最重要的两个数组，s[i][j]：点i-1 和 j 和这个值k之间有最小权 //min_w[i][j] ：点i-1....... j 的最小权值 int s[VERTEX_MAXNUM][VERTEX_MAXNUM]; double min_w[VERTEX_MAXNUM][VERTEX_MAXNUM]; //如果不加函数声明，输出返回值有错 void read_from_file( char *file ); double calculate_distance( double x1, double y1, double x2, double y2); void init_weight(); void print_out( int i, int j, int s[][VERTEX_MAXNUM] ); double min_weight( int i, int j ); void set_array_zero( int i, int j, double a[][VERTEX_MAXNUM]); double min_weight_recursion( int i, int j ); int time; #endif