itfan123AI人工智能斜率优化系列训练记录
原创前言
坡度优化一般用来进行优化dp调剂、出借等问题相关联的斜率优化训练，增强了一些DP思想。我选择了在老校长留下的课题领域进行实践，因为领域中的问题很多，以及个人长期不愿在单一主题上进行培训，所以打开这篇文章，记录了断断续续的培训效果和感悟。
记录
0x01
从一个简单的介绍性问题到一个简单的介绍性问题从一个简单的入门问题到一个简单的介绍性问题 玩具装箱 一开始，这个问题的意思和想法都比较简单，不会说话。
代码
#include
#define dd(x) cout<<#x<<" = "<K(q[t-1],i))
t--;
q[++t]=i;
}
cout< 0x02
小A表示最大场，小A表示最大场 仍然是介绍性的问题。原问题表面的问题意见，比较简单。其思想是保持一个公共前缀和一个梯形前缀，然后用与上一个问题相同的变体写出一个直线截取公式。唯一的区别是，问题是Ai这条线的斜率不能保证单调变化，所以在选择最优点时，需要对队列进行二分法，找出从那时起第一个小于这条线斜率的点。(前面的问题是因为直线的斜率是单调增加的，所以每次你选择最佳点时，只要第一个点的直线的斜率小于该直线的斜率就可以出来)。然后将这个问题调到最大，让排队保持一个上凸包。
代码
#include
#define dd(x) cout<<#x<<" = "<K(q[t],q[t-1]))
--t;
q[++t]=i;
}
cout< 0x03
HDU2993 这个问题的想法并不是很难，但我不知道为什么要考卡，挺恶心的，比较多low的IO优化还是过不去，我优化还是过不去，我优化还是过不去T打了十几个回合后，我用了前辈的，十几个回合后，我用了前辈的，我用了前辈的fread读入板只通过了。所以极力不建议你这样做，大脑AC这就是一切所需要的。一切都会好的。就这样。就这样。
其思想是在给定一系列长度n的情况下，找到长度不小于k且平均值最大的子段。换句话说，找到所有的点(i,sum[i])中具有最高坡度的两点的坡度
不难认为，我们应该保持一个较低的凸壳(因为它上面的点肯定不能与它后面的点形成更优的解)，然后我们通常可以二分法找到最优点，但它可以根据这个问题的性质找到，因为sum[i]是递增的，所以每次找到更好的点时，它之前的点可以直接丢弃(它们不能与稍后添加的新点形成更大的坡度)。因此，复杂度可以为O(N)。
代码(再次，不推荐)代码(再次，不推荐)代码(再次，不推荐)
#include
#define dd(x) cout<<#x<<" = "< ",ans); } return 0; }
0x04
HDU 3045 其余为常规坡度优化，其余为常规坡度优化DP斜率的比较斜率不应该有错。特别注意斜率的比较，不要写错(方便做差值时取绝对值。WA(十几轮)，为了避免准确度误差，建议用乘法形式写比较。
代码
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],sum[maxn],f[maxn];
int q[maxn],h,t;
ll dy(int i,int j)
{
return f[i]-sum[i]+i*a[i+1]-f[j]+sum[j]-j*a[j+1];
}
ll dx(int i,int j)
{
return a[i+1]-a[j+1];
}
ll getf(int i,int j)
{
return f[i]+sum[j]-sum[i]-a[i+1]*(j-i);
}
int main()
{
int n,k;
while (scanf("%d%d",&n,&k)!=EOF)
{
for (int i=1;i<=n;++i)
scanf("%I64d",&a[i]);
sort(a+1,a+1+n);
for (int i=1;i<=n;++i)
sum[i]=sum[i-1]+a[i];
h=t=0;
for (int i=k;i<=n;++i)
{
int j=i-k;
if (j>=k)
{
while (h ",f[n]); } return 0; }
0x05
POJ 1180 ,这个问题问得很好。这个问题的意思相当繁琐，所以我们建议直接查看问题的原始表面。
这个问题也是很常规的用斜率优化的部分，更巧妙的是如何优化这个维度的枚举分组数，使复杂度降低到O(N)。可以发现，要知道该当前组的结束时间与先前划分了多少组有关，在这种情况下，必须列举转移。但换句话说，我们可以考虑每个分组对后续分组的成本的影响，并预先计算到当前组的成本s对全球答案的贡献对全球答案的贡献对全球答案的贡献,这样，传输不需要考虑前一个分组对当前分组的影响(因为它已经在前一个分组中计算过)。因此，转移方程可以写为f(j)=min{f(i)+(tsum[j]+s)(fsum[j]-fsum[i])+s(fsum[n]-fsum[j])}(0<=i<j),有了这个转移方程，剩下的就是通过以下方式优化坡度i对枚举进行了优化，以实现线性复杂性。
#include
#include
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
const int maxn=1e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll fsum[maxn],tsum[maxn],dp[maxn];
int q[maxn],h,t,s,n;
inline ll dy(int i,int j)
{
return dp[i]-dp[j];
}
inline ll dx(int i,int j)
{
return fsum[i]-fsum[j];
}
inline ll getv(int i,int j)
{
return dp[i]+(tsum[j]+s)*(fsum[j]-fsum[i])+s*(fsum[n]-fsum[j]);
}
int main()
{
while (cin>>n)
{
cin>>s;
for (int i=1;i<=n;++i)
{
scanf("%lld%lld",&tsum[i],&fsum [i]);
tsum[i]+=tsum[i-1],fsum[i]+=fsum[i-1];
}
t=h=0;
for (int j=1;j<=n;++j)
{
while (h 0x06
HDU 3480 第一个问题与第一个玩具盒相同，只是对组数有额外的限制，但其他问题完全相同。由于空间限制，我们首先枚举组的数量，以便每次清空队列以供重复使用。请注意，组的数量为k问题的答案是按分组编号给出的k-1答案是从问题的答案转移到问题的，注意边界点，详细信息见代码
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e4+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],f[maxn>>1][maxn];
int q[maxn],h,t;
inline ll dy(int i,int j,int k)
{
return f[k][i]+a[i+1]*a[i+1]-f[k][j]-a[j+1]*a[j+1];
}
inline ll dx(int i,int j)
{
return a[i+1]-a[j+1];
}
inline ll getf(int i,int j,int k)
{
return f[k-1][i]+(a[j]-a[i+1])*(a[j]-a[i+1]);
}
int main()
{
int T;
cin>>T;
for (int cas=1;cas<=T;++cas)
{
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for (int j=1;j<=n;++j)
f[1][j]=(a[j]-a[1])*(a[j]-a[1]);
for (int k=2;k<=m;++k)
{
h=t=0;
q[0]=k-1;
for (int j=k;j<=n;++j)
{
while (h ",cas,m>n?0ll:f[m][n]); } return 0; }
0x07
HDU 2829 这个问题将区间的值定义为区间中任意两个数字的乘积之和。在考虑了较长时间后对区间值的表示，区间[i,j]的值可以表示为的值可以表示为的值C[j]-C[i]-sum[i]*(sum[j]-sum[i]),C[i]表示前缀i这个想法的价值是和上一个问题一样对待的，没有什么坑坑洼洼的，只是注意边界。
代码
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e3+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn][maxn],a[maxn],sum[maxn],c[maxn];
int q[maxn],h,t;
inline ll dy(int i,int j,int k)
{
return f[k][i]+sum[i]*sum[i]-c[i]-f[k][j]-sum[j]*sum[j]+c[j];
}
inline ll dx(int i,int j)
{
return sum[i]-sum[j];
}
inline ll getf(int i,int j,int k)
{
return f[k-1][i]+c[j]-c[i]-(sum[j]-sum[i])*sum[i];
}
int main()
{
int n,m;
while (scanf("%d%d",&n,&m)&&n)
{
++m;
for (int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for (int i=2;i<=n;++i)
c[i]=c[i-1]+sum[i-1]*a[i];
for (int j=1;j<=n;++j)
f[1][j]=c[j];
for (int k=2;k<=m;++k)
{
h=t=0;
q[0]=k-1;
for (int j=k;j<=n;++j)
{
while (h ",f[m][n]); } return 0; }
0x08
HDU 3507 ,简化版的玩具盒，没有长度限制和分组限制，入门级
代码
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn],a[maxn],sum[maxn];
int q[maxn],h,t,M;
inline ll dy(int i,int j)
{
return f[i]+sum[i]*sum[i]-f[j]-sum[j]*sum[j];
}
inline ll dx(int i,int j)
{
return sum[i]-sum[j];
}
inline ll getf(int i,int j)
{
return f[i]+(sum[j]-sum[i])*(sum[j]-sum[i])+M;
}
int main()
{
int n;
while (scanf("%d%d",&n,&M)!=EOF)
{
for (int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
h=t=0;
for (int i=1;i<=n;++i)
{
while (h ",f[n]); } return 0; }
0x09
POJ 3709 ,有长度限制，无分组限制，正则解
#include
#include
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
const int maxn=5e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll f[maxn],a[maxn],sum[maxn];
int q[maxn],h,t,M;
inline ll dy(int i,int j)
{
return f[i]-sum[i]+i*a[i+1]-f[j]+sum[j]-j*a[j+1];
}
inline ll dx(int i,int j)
{
return a[i+1]-a[j+1];
}
inline ll getf(int i,int j)
{
return f[i]+sum[j]-sum[i]-(j-i)*a[i+1];
}
int main()
{
int T;
cin>>T;
while (T--)
{
int n,k;
scanf("%d%d",&n,&k);
for (int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
h=t=0;
for (int i=k;i<=n;++i)
{
int j=i-k;
if (j>=k)
{
while (h ",f[n]); } return 0; }
0x0A
HDU 3669 ,每个人都有一个高，每个人都有一个高，每个人都有一个高h和宽w如果一个人只有在高度和宽度不大于门的高度时才能通过门H和宽W。建造不超过k门，每个门标识一个门，每个门标识一个门，每个门标识一个W和H每扇门的成本就是每扇门的成本每扇门的成本就是每扇门的成本W*H通过让所有人至少通过一扇门，可以找到最低成本。为了便于计算，我们执行特定的预处理，其中我们按照人的一个属性以升序对其进行排序，然后结果序列按另一个属性以降序进行排序(即，消除那些h和w比明显不影响答案的人小)，在这一点上得到的序列满足第一维增加和第二维减少。显然，进入同一扇门的人在顺序上必须是连续的。运行一个DP对于分组，只需一次传递即可完成坡度优化。
有关预处理的详细信息，请参阅代码。有关预处理的详细信息，请参阅代码。
#include
#define fi first
#define se second
#define dd(x) cout<<#x<<" = "<=a[cnt].se)
--cnt;
a[++cnt]=a[i];
}
m=min(m,cnt);
for (int i=1;i<=cnt;++i)
f[1][i]=a[i].fi*a[1].se;
for (int k=2;k<=m;++k)
{
h=t=0;
q[0]=k-1;
for (int j=k;j<=cnt;++j)
{
while (h ",ans); } }
0x0B
311B - Cats Transport 丽贝卡-奈特目前是Insider的高级记者，报道职业和工作场所。在此之前，她是一名自由记者和卫斯理大学的讲师.她的作品曾在“纽约时报”、“今日美国”和“金融时报”上发表.ai贪婪的人知道，每个饲养员都必须负责捡起猫的连续部分。因此，对于这个数组a进行dp分组、坡度优化。用斜率优化进行分组。
#include
#define dd(x) cout<<#x<<" = "< "
define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair P;
typedef priority_queue BQ;
typedef priority_queue,greater > SQ;
const int maxn=1e5+10,mod=1e9+7,INF=0x3f3f3f3f;
ll a[maxn],f[105][maxn],sumd[maxn],suma[maxn];
int q[maxn],h,t;
ll dy(int i,int j,int k)
{
return f[k][i]+suma[i]-f[k][j]-suma[j];
}
ll dx(int i,int j)
{
return i-j;
}
ll getf(int i,int j,int k)
{
return f[k-1][i]+a[j]*(j-i)-suma[j]+suma[i];
}
int main()
{
int n,m,p;
cin>>n>>m>>p;
for (int i=2;i<=n;++i)
{
scanf("%I64d",&sumd[i]);
sumd[i]+=sumd[i-1];
}
for (int i=1;i<=m;++i)
{
ll h,t;
scanf("%I64d%I64d",&h,&t);
a[i]=t-sumd[h];
}
sort(a+1,a+1+m);
for (int i=1;i<=m;++i)
{
suma[i]=suma[i-1]+a[i];
f[1][i]=i*a[i]-suma[i];
}
for (int k=2;k<=p;++k)
{
h=t=0;
q[0]=k-1;
for (int j=k;j<=m;++j)
{
while (h 0x0C
货币兑换Cash ,从贪婪的想法来看，很明显，每次你买入或卖出，你肯定会花光所有的钱，或者卖掉所有的金券。因此f(i)表示到第i上帝手中的最大数额的钱。f(i)=max(A(j)a[i]+B(j)b[i]),其中A(j)表示第j花完所有的钱都可以拿到天花完所有的钱可以拿到所有的钱A金色门票的数量。金券的数量。金券数量。金券的数量B(j)一样的。轻微的变形就会产生-B(j)=a[i]/b[i]*A(j)-f[i]/b[i]。可以发现，水平坐标A(j)和斜率a[i]/b[i]两者都不是单调乏味的。它们都不是单调的。所有这些都不是单调的。没有一个是单调的。
这可以通过使用平衡树来维护动态凸包或cdq要解决的分区问题。我选择了这里CDQ来解决这个问题。来解决这个问题。来解决这个问题。来解决这个问题。
可能的想法是，对于每个人，可能的想法是，对于每个人，一般的想法是，对于每个人，近似的想法是f(i)，它的决策点必须在它的左边，换句话说，每个点只影响它右边的点。用于求解区间[l,r]内的f值，则可以首先递归地求解它的左区间，然后在完成f然后完成处理，然后对左区间内重新排序的点保持一个凸包，对于右区间上的点可以对这个凸包进行二分，找出要更新的决策点，然后递归地求解右区间内的影响，完成后再对右区间内的f还会处理这些值。在这一点上，这个很大的间隔f该值将被处理。将处理这些值。值处理完成。值处理完成。
#include
#define dd(x) cout<<#x<<" = "< 转载于:https://www.cnblogs.com/orangee/p/10661996.html
版权声明
所有资源都来源于爬虫采集,如有侵权请联系我们,我们将立即删除
作者文章
- 解决SolidWorks2019许可证错误-85440 3个月前 (02-11)
- 解决sklearn.datasets.fetch_20newsgroups下载速度慢的问题 3个月前 (02-11)
- 解决sklearn.datasets.fetch_20newsgroups下载报错问题分享 3个月前 (02-11)
- 解决Scratch3.0scratch-hex文件下载失败问题 3个月前 (02-11)
- 解决RHEL7无法使用YUM源的问题 3个月前 (02-11)