StoneMerge
今天搞了一天石子合并
几个版本
直接循环数组，每次O(n^3), 总时间O(n^4)，复杂度太高了
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[1000][1000];
int a[1000],n;
int stonemax()
{
for(int i=0;i<=n-1;i++)
dp[i][i]=0;
for(int len=2;len<=n;len++)
{
for(int i=0;i<n;i++)
{
int j=i+len-1;
if(j>=n)
break;
//int maxn=0,minn=0x7fffffff;
int sum=0;for(int l=i;l<=j;l++)sum+=a[l];
int maxn=dp[i][i]+dp[i+1][j]+sum;
for(int k=i+1;k<=j-1;k++)
{
maxn=max(maxn,dp[i][k]+dp[k+1][j]+sum);
}
dp[i][j]=maxn;
}
}
return dp[0][n-1];
}
int stonemin()
{
for(int i=0;i<=n-1;i++)
dp[i][i]=0;
for(int len=2;len<=n;len++)
{
for(int i=0;i<n;i++)
{
int j=i+len-1;
if(j>=n)
break;
//int maxn=0,minn=0x7fffffff;
int sum=0;for(int l=i;l<=j;l++)sum+=a[l];
int minn=dp[i][i]+dp[i+1][j]+sum;
for(int k=i+1;k<=j-1;k++)
{
minn=min(minn,dp[i][k]+dp[k+1][j]+sum);
}
dp[i][j]=minn;
}
}
return dp[0][n-1];
}
int main()
{
freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int tmp,maxn=stonemax(),minn=stonemin();
for(int loop=1;loop<n;loop++)
{
tmp=a[0];
for(int i=0;i<n-1;i++)
a[i]=a[i+1];
a[n-1]=tmp;
maxn=max(maxn,stonemax());
minn=min(minn,stonemin());
}
printf("%d %d\n",minn,maxn);
}
}
扩展数组，然后DP状态扩大，空间扩了一倍，编程复杂度后面的低，时间O(n^3)
然后一直出了一个问题，就是i没有扩展到0-2n-1, 因为后面的子问题状态可能起点会 n-2n-1的范围里，一直都没有想到这个点。这里还要感谢瞿神
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[1000][1000];
int a[1000],n;
int stonemax()
{
for(int i=0; i<=n-1; i++)
dp[i] [i] =0;
for(int len=2; len<=n; len++)
{
for(int i=0; i<n; i++)
{
int j=i+len-1;
if(j>=n)
break;
int sum=0;
for(int l=i; l<=j; l++)sum+=a[l] ;
int maxn=dp[i] [i] +dp[i+1][j] +sum;
for(int k=i+1; k<=j-1; k++)
{
maxn=max(maxn,dp[i] [k] +dp[k+1][j] +sum);
}
dp[i] [j] =maxn;
}
}
return dp[0][n-1];
}
int stonemin()
{
for(int i=0; i<=n-1; i++)
dp[i] [i] =0;
for(int len=2; len<=n; len++)
{
for(int i=0; i<n; i++)
{
int j=i+len-1;
if(j>=n)
break;
int sum=0;
for(int l=i; l<=j; l++)sum+=a[l] ;
int minn=dp[i] [i] +dp[i+1][j] +sum;
for(int k=i+1; k<=j-1; k++)
{
minn=min(minn,dp[i] [k] +dp[k+1][j] +sum);
}
dp[i] [j] =minn;
}
}
return dp[0][n-1];
}
int stonemax_mod()
{
for(int i=0; i<=n-1; i++)
dp[i] [i] =0;
for(int len=2; len<=n; len++)
{
for(int i=0; i<=n-1; i++)
{
int j=(i+len-1)%n;
int sum=0;
if(i<j)
{
for(int l=i; l<=j; l++)sum+=a[l] ;
}
else
{
for(int l=i; l<=n-1; l++)sum+=a[l] ;
for(int l=0; l<=j; l++)sum+=a[l] ;
}
int maxn=0;
if(i<j)
{
for(int k=i; k<=j-1; k++)
maxn=max(maxn,dp[i] [k] +dp[k+1][j] +sum);
}
else
{
for(int k=i; i<=n-1; i++)
maxn=max(maxn,dp[i] [k] +dp[k+1][j] +sum);
for(int k=0; k<=j-1; k++)
maxn=max(maxn,dp[i] [k] +dp[k+1][j] +sum);
}
dp[i] [j] =maxn;
}
}
int maxn=0;
for(int i=0; i<=n-1; i++)
maxn=max(maxn,dp[i] [(i-1+n)%n]);
return maxn;
}
int stonemax_extendarray()
{
for(int i=0; i<=n-1; i++)
dp[i] [i] =0,a[n+i]=a[i] ;
int maxs=0;
for(int len=2; len<=n; len++)
{
for(int i=0; i<2*n; i++)
{
int j=i+len-1;
if(j>=2*n) break;
int sum=0;
for(int l=i; l<=j; l++)sum+=a[l] ;
int maxn=0;
for(int k=i; k<=j-1; k++)
{
maxn=max(maxn,dp[i] [k] +dp[k+1][j] +sum);
}
dp[i] [j] =maxn;
}
}
for(int i=0; i<n; i++)maxs=max(maxs,dp[i] [n-1+i]);
return maxs;
}
int stonemin_extendarray()
{
for(int i=0; i<=n-1; i++)
dp[i] [i] =0,a[n+i]=a[i] ;
int mins=0x7fffffff;
for(int len=2; len<=n; len++)
{
for(int i=0; i<2*n; i++)
{
int j=i+len-1;
if(j>=2*n)break;
int sum=0;
for(int l=i; l<=j; l++)sum+=a[l] ;
int minn=0x7fffffff;
for(int k=i; k<=j-1; k++)
{
minn=min(minn,dp[i] [k] +dp[k+1][j] +sum);
}
dp[i] [j] =minn;
}
}
for(int i=0; i<n; i++)mins=min(mins,dp[i] [n-1+i]);
return mins;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
for(int i=0; i<n; i++)
scanf("%d",&a[i] );
int tmp,minn=stonemin_extendarray(),maxn=stonemax_extendarray();
printf("%d %d\n",minn,maxn);
}
}
不取模，空间压缩了，也是O(n^3),空间降了，伟哥的代码
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int MAXINT = 2147483647;
struct MinSum{
public:
int get_min_score(vector<int> const &stones){
vector<int> sum(stones.size(), 0);
vector<vector<int> > dp(stones.size(), sum);
sum[0] = stones[0];
for (int i = 1; i < stones.size(); ++ i)sum[i] = sum[i - 1] + stones[i];
for (int j = 1; j < stones.size(); ++ j){
for (int i = 0; i < stones.size(); ++ i){
dp[i][j] = MAXINT;
for (int k = 0; k <j; ++ k){
int cur_temp = dp[i][k] + dp[(i + k + 1) % stones.size()][j - k - 1];
dp[i][j] = (dp[i][j] > cur_temp ? cur_temp : dp[i][j]);
}
int tail_index = (i + j) % stones.size();
int cur_sum_temp = 0;
if (tail_index > i)cur_sum_temp = sum[tail_index] - (i == 0 ? 0 : sum[i - 1]);
else cur_sum_temp = sum[sum.size() - 1] - (i == 0 ? 0 : sum[i - 1]) + sum[tail_index];
dp[i][j] += cur_sum_temp;
}
}
int result = dp[0][stones.size() - 1];
for (int i = 1; i < stones.size(); ++ i)result = (result < dp[i][stones.size() - 1] ? result : dp[i][stones.size() - 1]);
return result;
}
};
struct MaxSum{
public:
int get_max_score(vector<int> const &stones){
vector<int> sum(stones.size(), 0);
vector<vector<int> > dp(stones.size(), sum);
sum[0] = stones[0];
for (int i = 1; i < stones.size(); ++ i)sum[i] = sum[i - 1] + stones[i];
for (int j = 1; j < stones.size(); ++ j){
for (int i = 0; i < stones.size(); ++ i){
dp[i][j] = 0;
for (int k = 0; k <j; ++ k){
int cur_temp = dp[i][k] + dp[(i + k + 1) % stones.size()][j - k - 1];
dp[i][j] = (dp[i][j] < cur_temp ? cur_temp : dp[i][j]);
}
int tail_index = (i + j) % stones.size();
int cur_sum_temp = 0;
if (tail_index > i)cur_sum_temp = sum[tail_index] - (i == 0 ? 0 : sum[i - 1]);
else cur_sum_temp = sum[sum.size() - 1] - (i == 0 ? 0 : sum[i - 1]) + sum[tail_index];
dp[i][j] += cur_sum_temp;
}
}
int result = dp[0][stones.size() - 1];
for (int i = 1; i < stones.size(); ++ i)result = (result > dp[i][stones.size() - 1] ? result : dp[i][stones.size() - 1]);
return result;
}
};
class Solution{
private:
public:
void solve(){
//ifstream infile("187in.txt");
//cin.rdbuf(infile.rdbuf());
int num_stone;
while (cin >> num_stone){
vector<int> stones(num_stone, 0);
for (int i = 0; i < num_stone; ++ i)cin >> stones[i];
MinSum min_s;
MaxSum max_s;
cout << min_s.get_min_score(stones) << ' ' << max_s.get_max_score(stones) << endl;
}
}
};
int main(){
Solution so;
so.solve();
return 0;
}
ahdoc大神说有n^2算法，要给予一个不等式，另外ACRush还有一个nlogn的高端算法，基于斐波那契堆的贪心算法，这个就不去深究了。