题目：acdream 1222 Quantization Problem

题意：给出一个序列 a ，然后给出一个 n * m 的矩阵，让你从这个矩阵中选出一个序列k，使得sum（abs（ki - ai））尽可能的小，首先第一个数只能在矩阵的第一行选第 x 个，然后以后每个在第 x%n 行选，依次选出最小即可。每个点可以选多次、

分析：这个题目难度在于题意，题意读懂了就简单了。

很明显的一个dp题目，我们定义状态：dp 【i】【j】 ：选第 i 个数 在第 j 列的最小和

则转移方程：dp 【i】【j】 = dp [ i - 1 ] [ k ] + abs ( a [ i ] - mp [ k % s ] [ j ] ) ; k是枚举的前一次在第k行选

然后用一个pre数组保存一下路径就ok

AC代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int inf = 0x3f3f3f3f; const int N = 1200; const int M = 130; int dp[N][M]; int mp[M][M]; int pre[N][M]; int a[N]; int main() { //freopen("Input.txt","r",stdin); int n; int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0; i
       
         res; int i = n-1; while(i != -1) { res.push_back(rec); rec = pre[i--][rec]; } for(int i = res.size() - 1; 0 <= i; --i) { printf("%d%c",res[i],i==0?'\n':' '); } } return 0; }