acdream 1222 Quantization Problem [dp]

本是古典何须时尚 2022-08-13 00:36 157阅读 0赞

题目：[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 <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    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<n; i++)
                scanf("%d",&a[i]);
            int s,c;
            scanf("%d%d",&s,&c);
            for(int i=0; i<s; i++)
            {
                for(int j=0; j<c; j++)
                    scanf("%d",&mp[i][j]);
            }
            memset(dp,inf,sizeof(dp));
            for(int i=0; i<c; i++)
            {
                int ff = abs(a[0]-mp[0][i]);
                dp[0][i]=min(dp[0][i],ff);
                //printf("%d ",dp[0][i]);
            }
            memset(pre,0,sizeof(pre));
            for(int i=1; i<n; i++)
            {
                for(int j=0; j<c; j++)
                {
                    for(int k=0; k<c; k++)
                    {
                        int ff = dp[i-1][k] + abs(a[i]-mp[k%s][j]); //枚举在所有行取。
                        if(ff<dp[i][j])
                        {
                            dp[i][j]=ff;
                            pre[i][j]=k;
                        }
                    }
                    //printf("%d ",dp[i][j]);
                }
                //printf("\n");
            }
            int ans = inf, rec;
            for(int i = 0; i < c; i++)
            {
                if(dp[n-1][i] < ans)
                {
                    ans = dp[n-1][i];
                    rec = i;
                }
            }
            printf("%d\n", ans);
            vector<int> 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;
    }

[acdream 1222 Quantization Problem]: http://acdream.info/problem?pid=1222