首页 > 代码库 > sgu-205 Quantization Problem

sgu-205 Quantization Problem

题目大意:

给定一个n,然后一个数组S[n],然后给你一个m*s(m<=s)的矩阵A,然后要你求出一个数列k,满足∑i=1~n |  A[ k[i-1]  %m  ][ k[i] ]  -S[i] | 最小,输出最小值和其中一组解



解题思路:

显然这是一道明显的dp题,设f[i][j]表示对于k[i]取j的时候,最小值是多少,然后dp就行了

f[i][j]=MIN(f[i-1][g]+a[g%m][j])  (g=1~s  因为m<=s)

最后记录一个father输出就行了



AC代码:


#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MIN(a,b) ((a)>(b)?(b):(a))

using namespace std;
int t,n,m;
int s[1010]={0};
int a[150][150]={{0}};
int f[1010][150]={{0}};
int father[1010][150]={{0}};

void prt(int a,int b)
{
	if(a==0)
		return;
	prt(a-1,father[a][b]);
	cout<<b;
	if(a<t)
		cout<<' ';
	return;
}

int main()
{
	cin>>t;
	for(int i=1;i<=t;i++)
		scanf("%d",&s[i]);
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=t;i++)
	{
		for(int j=0;j<m;j++)
		{
			for(int k=0;k<m;k++)
			{
				int tmp=f[i-1][k]+abs(a[k%n][j]-s[i]);
				if(tmp<f[i][j])
				{
					father[i][j]=k;
					f[i][j]=tmp;
				}
			}
		}
	}
	int ans=2e9,ansp=0;
	for(int i=0;i<m;i++)
		if(ans>f[t][i])
		{
			ans=f[t][i];
			ansp=i;
		}
	cout<<ans<<endl;
	prt(t,ansp);
	return 0;
}


ni=1|
i?1
dm,Ki
?Si
ni=1ni=1|AKi?1modm,Ki?Si|最小。
ni=1ni=1ni=1ni=1

sgu-205 Quantization Problem