acdream 1222 Quantization Problem [dp]

acdream 1222 Quantization Problem [dp]

題目：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;
}