本文主要是介绍jzoj3046. 【NOIP2012模拟10.23】游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
jzoj3046. 【NOIP2012模拟10.23】游戏
- 题目
- Description
- Input
- Output
- Sample Input
- Sample Output
- Hint
- 分析
- CODE
题目
Description
游戏规则如下:给定两个正整数数列,一个游戏者通过若干次操作完成游戏。每一次操作,选择两个正整数k1和k2。将第一个数列的最后连续k1个数删除,它们的和记为S1;将第二个数列的最后连续K2个数删除,它们的和记为S2。这一次操作的得分就是(S1-K1)* (S2-K2 )。直到两个数列都清空了为止,所以不允许一个数列空了,而另一个数列中还有数。游戏的总得分就是每一次操作的得分总和。求最小的总得分。
Input
第一行是两个整数L1和L2,分别表示第一个数列和第二个数列的初始长度。
第二行有L1个正整数,是第一个数列的数。
第三行有L2个正整数,是第二个数列的数。
数列中的数都不超过1000。
Output
一个整数,表示最小的总得分。
Sample Input
3 2
1 2 3
1 2
Sample Output
2
Hint
对于20%的数据,L1,L2<=20;
对于40%的数据,L1,L2<=200;
对于100%的数据,1<=L1,L2<=2000。
分析
由题意知:每次的和S1、S2都需要减去K1、K2,所以我们可以预处理将两个数列中的每一个数都-1
设f[i][j]为第一个数列剩余i个数,第二个数列剩余j个数时的最小总得分
f[i][j]=min(f[i+1][j],f[i][j+1],f[i][j],f[i+1][j+1])+a[i+1]*b[j+1];
CODE
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int l1,l2,a[2010],b[2010],f[2010][2010];int main(){scanf("%d%d",&l1,&l2);for (int i=1;i<=l1;i++){scanf("%d",&a[i]);a[i]--;}for (int i=1;i<=l2;i++){scanf("%d",&b[i]);b[i]--;}memset(f,1000000,sizeof(f));f[l1][l2]=0;for (int i=l1-1;i>=0;i--){for (int j=l2-1;j>=0;j--){f[i][j]=min(f[i+1][j],f[i][j+1]);f[i][j]=min(f[i][j],f[i+1][j+1])+a[i+1]*b[j+1];} }printf("%d\n",f[0][0]);return 0;
}
这篇关于jzoj3046. 【NOIP2012模拟10.23】游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!