目录
1 石子合并
2 环形石子合并
3 能量项链
4 凸多边形的划分
5 加分二叉树
6 棋盘分割(记忆化搜索+二维前缀和)
1 石子合并
282. 石子合并 - AcWing题库
#include
using namespace std;
const int N=310;
int s[N],f[N][N];//s是前缀和
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];//求一遍前缀和
}
for(int len=2;len<=n;len++)//枚举l到r之间的长度
for(int l=1;l+len-1<=n;l++)//枚举l
{
int r=l+len-1;//根据长度和l获得r
f[l][r]=0x3f3f3f3f;//因为更新最小值,则把该数定义成最大值
for(int k=l;k
2 环形石子合并
枚举环形,我们都可以拉伸成线性,数量由n->2n
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
线形石子合并跟上面的状态分析一样,只不过多开个g来存最大值
#include
using namespace std;
const int N=410;
int s[N],f[N][N],g[N][N];//s是前缀和,f记录最小值,g记录最大值
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[n+i]=s[i];//复制后面的重复的一段
}
for(int i=1;i<=2*n;i++) s[i]+=s[i-1];//求一遍前缀和
for(int len=2;len<=n;len++)//枚举l到r之间的长度
for(int l=1;l+len-1<=2*n;l++)//枚举2n个数,也就是还变成线形的数
{
int r=l+len-1;//根据长度和l获得r
f[l][r]=0x3f3f3f3f;//因为更新最小值,则把该数定义成最大值
g[l][r]=-0x3f3f3f3f;//因为更新最大值,则把该数定义成最小值
for(int k=l;k
3 能量项链
因为这里也是环形跟上一题一样要进行拉伸成线形
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
#include
using namespace std;
const int N=210;
int w[N],f[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
w[n+i]=w[i];//因为是环形,转化成线形
}
for(int len=3;len<=n+1;len++)//枚举l到r的长度
for(int l=1;l+len-1<=2*n;l++)
{
int r=len+l-1;
f[l][r]=-0x3f3f3f3f;//因为要求最大值,所以初始化为负无穷
for(int k=l+1;k
4 凸多边形的划分
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
由于这题每个w[i]都是10^9,则三个乘以的话就10^27,则要自己写个高精度加法与乘法
状态分析跟上一题一样
//没加高精度的模板,过不了
#include
using namespace std;
const int N=210;
int w[N],f[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
for(int len=3;len<=n;len++)//枚举l到r的长度
for(int l=1;l+len-1<=n;l++)
{
int r=len+l-1;
f[l][r]=0x3f3f3f3f;//因为要求最小值,所以初始化为正无穷
for(int k=l+1;k
AC加了高精度
#include
using namespace std;
typedef long long ll;
const int N=55,M=35;
ll w[N],f[N][N][M];
void add(ll a[],ll b[])//高精度加法
{
static ll c[M];
memset(c,0,sizeof c);
ll t=0;
for(int i=0;i=0;i--)
if(a[i]>b[i]) return true;
else if(a[i]=0) cout<>n;
for(int i=1;i<=n;i++) cin>>w[i];
ll temp[M];
for(int len=3;len<=n;len++)//枚举l到r的长度
for(int l=1;l+len-1<=n;l++)
{
int r=len+l-1;
//f[l][r]=0x3f3f3f3f;
f[l][r][M-1]=1;//因为要求最小值,所以初始化为正无穷,最高位是1,说明1e34,已经很大了
for(int k=l+1;k
5 加分二叉树
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
输出时是要求前序遍历,则递归输出根左右
#include
using namespace std;
typedef long long ll;
const int N=35;
int w[N],f[N][N],g[N][N];//f记录[l,r]区间的分数,g记录[l,r]的根节点
void dfs(int l,int r)//前序遍历是根左右
{
if(l>r) return ;
int root=g[l][r];//根
cout<>n;
for(int i=1;i<=n;i++) cin>>w[i];
memset(f,-0x3f,sizeof f);//因为要求最大值,则初始化为负无穷
for(int len=1;len<=n;len++)//枚举[l,r]的长度
for(int l=1;l+len-1<=n;l++)//枚举l
{
int r=l+len-1;
if(len==1) f[l][r]=w[l],g[l][r]=l;//假如只有自己,则分数是自己,根也是自己
else
{
for(int k=l;k<=r;k++)//枚举[l,r]之间的根节点
{
int left=k==l?1:f[l][k-1];//假如k是等于l,说明l到k没有左子树,则分数为1
int right=k==r?1:f[k+1][r];//假如k是等于r,说明l到k没有右子树,则分数为1
int socre=left*right+w[k];//算一下分数
if(f[l][r]
6 棋盘分割(记忆化搜索+二维前缀和)
321. 棋盘分割 - AcWing题库
#include
using namespace std;
typedef long long ll;
const int N=15,M=9;
const double INF=1e9;
int s[M][M];//二维前缀和
double f[M][M][M][M][N];
double X;//平均数
int n;
double get(int x1,int y1,int x2,int y2)//求子矩阵的方差
{
double sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]-X;//求方差
return sum*sum/n;
}
double dp(int x1,int y1,int x2,int y2,int k)//记忆化搜索
{
double &v=f[x1][y1][x2][y2][k];
if(v>=0) return v;//假如已经处理过直接返回他的值
if(k==1) return v=get(x1,y1,x2,y2);//假如切割是一次,则就是最后一块子矩阵,则直接求他的值,不用再切割
v=INF;//因为要求最小值,初始化为正无穷
for(int i=x1;i>n;
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和
}
memset(f,-1,sizeof f);//初始化为-1,便于记忆化搜索
X=(double)s[8][8]/n;//求平均数
printf("%.3lf\n",sqrt(dp(1,1,8,8,n)));//输出根号方差,即均方差
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)