区间DP，复习一下
石子合并
最经典的题了
#include <bits/stdc++.h>
using namespace std;
#define imax 0x7fffffff
const int N=500;
int dp[N][N];
int a[N];
int sum[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int len=1;len<=n;len++)
{
for(int l=1;l<=n;l++)
{
int r=len+l;
if(r>n)
break;
dp[l][r]=imax;
for(int k=l;k<=r;k++)
{
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
注意的点主要有三个
1.边界的控制
2.初始化
3.特殊条件
比如这个题就是
CF607B Zuma
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[500+10][500+10];
int a[500+10];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=1e9;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i][i]=1;
}
for(int i=1;i<n;i++)
dp[i][i+1]=1+(a[i]!=a[i+1]);
for(int i=1;i<=n;i++)
{
for(int l=1;l<=n;l++)
{
int r=l+i-1;
if(r>n)
break;
if(a[l]==a[r])
{
dp[l][r]=min(dp[l][r],dp[l+1][r-1]);
}
for(int k=l;k<=r;k++)
{
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
思维题
D. Insert a Progression
题意：给定初始数组a，和一个含有x个元素的排列，要求把排列插入数组中并且让插入之后的数组的相邻项的差的绝对值之和最小。
分析
1.发现1 3 7和1 7的相邻项的差的绝对值之和相等均是6，所以应当尽可能的少造成波峰和波谷
2.根据观察，发现在中间的波峰或者波谷对于答案的贡献比两边的大，中间的会贡献两倍的差值
3.在观察发现，1 3 7这样数组，把3替换了之后新增的差值是替换值和3的差值的两倍
4.根据以上三条可以确定贪心思路
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N =2e5+100;
int a[N];
signed main()
{
int t;
for(cin>>t;t;t--)
{
int f,l;
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
f=min(a[1]-1,a[n]-1);
l=min(x-a[1],x-a[n]);
for(int i=1;i<=n;i++)
{
f=min(f,2*(a[i]-1));
l=min(l,2*(x-a[i]));
if(i>1)
ans+=abs(a[i]-a[i-1]);
}
f=max(f,0ll);
l=max(l,0ll);
ans+=f+l;
cout<<ans<<endl;
}
return 0;
}
待思考：这样不会选到同一个元素吗，，选到了真的合法吗，为什么
题意：给定初始数组b全为0，和一个数组a，用a数组每次可以让bi，加ai或者减ai，问：构造一个严格递增的数组b最少要几次操作
思路：枚举每一个点作为0的情况
我真的没想出来这个狗思路，什么啊这
看不懂自己跟着模拟一下
#include <bits/stdc++.h>
#define int long long
using namespace std;
long long n,a[5005],ans=1e18;
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
int pre=0,sum=0;
for(int j=i+1;j<=n;j++)
{
sum+=pre/a[j]+1;
pre=(pre/a[j]+1)*a[j];
}
pre=0;
for(int j=i-1;j>=1;j--)
{
sum+=pre/a[j]+1;
pre=(pre/a[j]+1)*a[j];
}
ans=min(ans,sum);
}
cout<<ans<<endl;
return 0;
}
