题解【POJ1157】LITTLE SHOP OF FLOWERS

先把题目意思说一下:

你有F束花,编号为\(1\)~\(F\)(\(1<=F<=100\)),\(V\)个花瓶,编号为\(1\) ~\(V\)(\(1<=V<=100\)),

一束花只能放到一个花瓶里,一个花瓶只能放一束花,并且花必须按编号放入花瓶,

即若编号为\(a\)的花放到编号为\(b\)的花瓶里,那么编号为\(a+1\) ~\(F\)的花只能放在编号为\(b+1\) ~\(V\)的花瓶里,

并且,第\(i\)束花放到第\(j\)个花瓶有一个美丽值\(a_{i,j}\)(\(-50<=a_{i,j}<=50\)),求将所有花放入花瓶的最大的美丽值.

解析

这题其实就和背包一样...

我们设\(f[i][j]\)表示将前\(i\)束花放入前\(j\)个花瓶里的最大美丽值,

那么考虑状态转移,

对于当前枚举到的\(i\),\(j\),

要么把\(i\)放入\(j\)中,即\(f[i][j]=f[i-1][j-1]+a[i][j]\),

要么就不放,即\(f[i][j]=f[i][j-1]\),

所以,两重循环扫一遍就行了(是不是感觉好简单)

上代码吧:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

int n,m;

int a[1001][1001];

int f[1001][1001];

int main(){

	n=read();m=read();

	memset(f,-0x3f,sizeof(f));

	for(int i=0;i<=m;i++) f[0][i]=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++) a[i][j]=read();

	for(int i=1;i<=n;i++){

		for(int j=i;j<=m;j++) f[i][j]=max(f[i][j-1],f[i-1][j-1]+a[i][j]);

	}

	printf("%d\n",f[n][m]);

	return 0;

}

巴特西

题解【POJ1157】LITTLE SHOP OF FLOWERS

先把题目意思说一下:

解析

最新文章

热门文章

巴特西

题解 【POJ1157】LITTLE SHOP OF FLOWERS

先把题目意思说一下:

解析

最新文章

热门文章

题解【POJ1157】LITTLE SHOP OF FLOWERS