个人网站建站,asp.net开发移动网站模板下载,物流网站怎么做,disqus wordpress传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给一个二维平面#xff0c;起点在(0,0)(0,0)(0,0)#xff0c;终点在(n,n)(n,n)(n,n)#xff0c;每次只能往上和往右走#xff0c;距离随意#xff0c;总步数不超过nnn#xff0c;每一步有一个代价cic_…传送门
文章目录题意思路题意
给一个二维平面起点在(0,0)(0,0)(0,0)终点在(n,n)(n,n)(n,n)每次只能往上和往右走距离随意总步数不超过nnn每一步有一个代价cic_ici定义从(0,0)(0,0)(0,0)到(n,n)(n,n)(n,n)总花费是∑ci∗disti\sum c_i*dist_i∑ci∗distidistidist_idisti是第iii步走的长度。
思路
我们假设一共走了kkk步那么说明我们拐了k−1k-1k−1个弯设每次走的步为dist1,dist2,dist3,...,distkdist_1,dist_2,dist_3,...,dist_kdist1,dist2,dist3,...,distk我们可以发现dist1dist3...ndist_1dist_3...ndist1dist3...ndist2dist4...ndist_2dist_4...ndist2dist4...n所以我们可以奇偶分开做就好啦。 分别统计一下奇数和偶数到当前位的cic_ici最小值让后让最小值走的步最多其他的disti1dist_i1disti1即可。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int c[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d,n);for(int i1;in;i) scanf(%d,c[i]);LL pre1,pre2,ans1,ans2;pre1pre20;ans1ans21e18;LL ans1e18;LL mi1,mi2; mi1mi21e18;for(int i1,c10,c20;in;i){if(i%21){mi1min(mi1,1ll*c[i]);c1;pre1c[i];if(i2) ansmin(ans,1ll*(n-c1)*mi1pre1ans2);ans11ll*(n-c1)*mi1pre1;}else{mi2min(mi2,1ll*c[i]);c2;pre2c[i];if(i2) ansmin(ans,1ll*(n-c2)*mi2pre2ans1);ans21ll*(n-c2)*mi2pre2;}}printf(%lld\n,ans);}return 0;
}
/**/
