NK1137 石子合并问题
题意：石子合并问题。DP问题。
我们先来考虑一条直线的问题，最小花费和最大花费方法是一样的，我们只考虑一种：我们先考虑一个子问题，要把从i 到j 的石子合并成一堆，肯定要先把它们合并成两堆；由于只允许相邻两堆合并，必然是i 到j 之间被分成了两段，设这个中间点是k，则这个方案可以表示为先把i 到k 合并，再把k + 1 到j 合并，然
后把得到的两堆合并，最后一次合并的花费为i 到j 所有石子的质量和，所以我们有dp[i; j] = min(dp[i; k] + dp[k + 1; j]) + weight[i; j]，简单地得到了O(N3) 的方法。
如果要考虑环的话，只需依次选择不同的头，即拆成n条不同的线段即可。
[cpp]
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int a[105];
int dp[105][105][2];
int n;
int mmax,mmin;
int weight(int i,int j)
{
int sum = 0;
for(int k=i;k<=j;k++) sum+=a[k];
return sum;
}
void solve()
{
memset(dp,0,sizeof(dp));
for(int i = n-1;i>=1;i--)
{
for(int j = i+1;j<=n;j++)
{
dp[i][j][0] = -INF,dp[i][j][1] = INF;
for(int k = i;k<j;k++)
{
dp[i][j][0] = max(dp[i][j][0],dp[i][k][0] + dp[k+1][j][0] + weight(i,j));
dp[i][j][1] = min(dp[i][j][1],dp[i][k][1] + dp[k+1][j][1] + weight(i,j));
}
}
}
mmax = max(mmax,dp[1][n][0]);
mmin = min(mmin,dp[1][n][1]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while(scanf(" %d",&n)!=EOF)
{
mmax = -INF,mmin = INF;
for(int i=1;i<=n;i++) scanf(" %d",&a[i]);
solve();
for(int i=2;i<=n;i++)
{
int last = a[1];
for(int i=1;i<n;i++) a[i] = a[i+1];
a[n] = last;
solve();
}
printf("%d\n",mmin);
printf("%d\n",mmax);
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int a[105];
int dp[105][105][2];
int n;
int mmax,mmin;
int weight(int i,int j)
{
int sum = 0;
for(int k=i;k<=j;k++) sum+=a[k];
return sum;
}
void solve()
{
memset(dp,0,sizeof(dp));
for(int i = n-1;i>=1;i--)
{
for(int j = i+1;j<=n;j++)
{
dp[i][j][0] = -INF,dp[i][j][1] = INF;
for(int k = i;k<j;k++)
{
dp[i][j][0] = max(dp[i][j][0],dp[i][k][0] + dp[k+1][j][0] + weight(i,j));
dp[i][j][1] = min(dp[i][j][1],dp[i][k][1] + dp[k+1][j][1] + weight(i,j));
}
}
}
mmax = max(mmax,dp[1][n][0]);
mmin = min(mmin,dp[1][n][1]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while(scanf(" %d",&n)!=EOF)
{
mmax = -INF,mmin = INF;
for(int i=1;i<=n;i++) scanf(" %d",&a[i]);
solve();
for(int i=2;i<=n;i++)
{
int last = a[1];
for(int i=1;i<n;i++) a[i] = a[i+1];
a[n] = last;
solve();
}
printf("%d\n",mmin);
printf("%d\n",mmax);
}
return 0;
}
补充：软件开发 , C++ ,
