动态规划_圆形石子合并
程序员文章站
2022-07-03 08:49:24
...
虽然会了动态规划的思想,但有些题,还是真心规划不明白啊。。。。。。
今天练习一下Rqnoj上的一道经典题——圆形石子合并(http://www.rqnoj.cn/problem/490)
分析一下题目给的样例(以下分析全部分析最小得分的情况),
(1)初始状态,得分为0,总得分为0
(2)先将绿色的4和蓝色的4合并,得分为8,总得分为8
(3)将蓝色的8和黄色的5合并,得分为13,总得分为21
(4)将绿色的13和红色的9合并,得分为22,总得分为43
因为合并的方式有很多种,比如在(1)中,我们也可以先合并绿色的4和黄色的5,当然这样的合并顺序会得到不同的总得分。
而依次实验这各种各样的合并方式,花销会非常大,会导致超出时间限制,所以,要采用动态规划的方法。
动态规划解法:
n :共有n堆石子
a[i]:存储第i堆石子的重量
fmin [i][j]:从第i堆开始,合并后面j个堆得到的最小值
sum [i][j]:从第i堆开始,到第i+j堆的总重量和。
初始化:
fmin[i][j]=0; (j=0)
状态转移方程:
fmin[i][j]=min{ fmin[i][k] + fmin[(i+k)%n][j-k]+ sum[i][j]} (0<k<j)
JAVA代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n =0;//共有n堆石子
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[] a = new int[n+1];//存储每堆石子的重量
a[0]=0;
for(int i1=1;i1<=n;i1++)//读入
{
a[i1]=sc.nextInt();
}
int[][] fmin = new int[n+1][n+1];//从第i个开始,合并后面j个得到的最小值
int[][] fmax = new int[n+1][n+1];//从第i个开始,合并后面j个得到的最大值
int[][] sum = new int[n+1][n+1];//从第i个开始,到第i+j个的数量和。
//初始化
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
fmin[i][j]=Integer.MAX_VALUE;
fmax[i][j]=Integer.MIN_VALUE;
if(j==0)
{
fmin[i][j]=0;
fmax[i][j]=0;
sum[i][j]=0;
}
else
{
int t1=i+j-1;
if(t1>n) t1=t1%n;
sum[i][j]=sum[i][j-1]+a[t1];
}
if(j==1)
{
fmin[i][j]=0;//sum[i][1];
fmax[i][j]=0;//sum[i][1];
}
}
}
//DP
for(int j=1;j<=n;j++)
{
for(int i =1;i<=n;i++)
{
//System.out.println("现在计算 "+i+"-"+(i+j-1)+":");
if(j==1)
{
}
else
{
for(int k =1;k<j;k++)
{
int t3=(i+k);
if(t3>n) t3=t3%n;
int t1=fmin[i][k] + fmin[t3][j-k] + sum[i][j];
int t2=fmax[i][k] + fmax[t3][j-k] + sum[i][j];
if(t1<fmin[i][j]) fmin[i][j]=t1;
if(t2>fmax[i][j]) fmax[i][j]=t2;
//System.out.println(i+"-"+(i+k-1)+"||"+(i+k)+"-"+(i+j-1));
//System.out.println("fmin["+i+"]["+k+"]"+"+"+"fmin["+t3+"]["+(j-k)+"]");
//System.out.println(fmin[i][k]+"+"+fmin[t3][j-k]+"+"+sum[i][j]+"="+fmin[i][j]);
}
}
}
}
/*for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
System.out.print(fmin[i][j]+" ");
}
System.out.println(" ");
}*/
int resule_min = Integer.MAX_VALUE;
int resule_max = Integer.MIN_VALUE;
for(int i1=1;i1<=n;i1++)
{
if(fmin[i1][n] < resule_min) resule_min=fmin[i1][n];
if(fmax[i1][n] > resule_max) resule_max=fmax[i1][n];
}
System.out.println(resule_min);
System.out.println(resule_max);
}
}
激动的写完之后,发现Rqnoj并不接受JAVA代码,为了验证,所以速度写个C++。
C++代码:
#include <iostream>
using namespace std;
#define INT_MIN (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX 2147483647 /* maximum (signed) int value */
int main()
{
int n =0;//共有n堆石子
cin>>n;
int a[120];//存储每堆石子的重量
a[0]=0;
for(int i1=1;i1<=n;i1++)//读入
{
cin>>a[i1];
}
int fmin[120][120];//从第i个开始,合并后面j个得到的最小值
int fmax[120][120];//从第i个开始,合并后面j个得到的最大值
int sum[120][120];//从第i个开始,到第i+j个的数量和。
//初始化
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
fmin[i][j]=INT_MAX;
fmax[i][j]=INT_MIN;
if(j==0)
{
fmin[i][j]=0;
fmax[i][j]=0;
sum[i][j]=0;
}
else
{
int t1=i+j-1;
if(t1>n) t1=t1%n;
sum[i][j]=sum[i][j-1]+a[t1];
}
if(j==1)
{
fmin[i][j]=0;//sum[i][1];
fmax[i][j]=0;//sum[i][1];
}
}
}
//DP
for(int j=1;j<=n;j++)
{
for(int i =1;i<=n;i++)
{
//System.out.println("现在计算 "+i+"-"+(i+j-1)+":");
if(j==1)
{
}
else
{
for(int k =1;k<j;k++)
{
int t3=(i+k);
if(t3>n) t3=t3%n;
int t1=fmin[i][k] + fmin[t3][j-k] + sum[i][j];
int t2=fmax[i][k] + fmax[t3][j-k] + sum[i][j];
if(t1<fmin[i][j]) fmin[i][j]=t1;
if(t2>fmax[i][j]) fmax[i][j]=t2;
//System.out.println(i+"-"+(i+k-1)+"||"+(i+k)+"-"+(i+j-1));
//System.out.println("fmin["+i+"]["+k+"]"+"+"+"fmin["+t3+"]["+(j-k)+"]");
//System.out.println(fmin[i][k]+"+"+fmin[t3][j-k]+"+"+sum[i][j]+"="+fmin[i][j]);
}
}
}
}
/*for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
System.out.print(fmin[i][j]+" ");
}
System.out.println(" ");
}*/
int resule_min = INT_MAX ;
int resule_max = INT_MIN ;
for(int i1=1;i1<=n;i1++)
{
if(fmin[i1][n] < resule_min) resule_min=fmin[i1][n];
if(fmax[i1][n] > resule_max) resule_max=fmax[i1][n];
}
cout<<(resule_min)<<endl;
cout<<(resule_max);
return 0;
}
上一篇: 石子合并问题(动态规划)
下一篇: 【CSS】LESS即学即用