A.
B.基础Dp.
设定dp【i】【2】：
①dp【i】【0】表示到位子i不建立糖果厂的最小花费。
②dp【i】【1】表示到位子i建立糖果厂的最小花费。
那么其状态转移方程不难写出：
dp【i】【1】=min（dp【i】【0】+w，dp【i】【1】+w）；
dp【i】【0】=min（dp【i】【0】，dp【j】【1】+从j+1到i所有到点j的距离和）；
注意初始化要足够大。
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define ll __int64 struct node { ll x,w; }a[3005]; ll dp[3005][2]; ll cost[3005][3005]; int cmp(node a,node b) { return a.x<b.x; } int main() { ll n; while(~scanf("%I64d",&n)) { memset(cost,0,sizeof(cost)); memset(dp,0,sizeof(dp)); for(ll i=1;i<=n;i++) { scanf("%I64d%I64d",&a[i].x,&a[i].w); } sort(a+1,a+1+n,cmp); dp[1][1]=a[1].w; dp[1][0]=1000000000000000000; for(ll i=1;i<=n;i++) { for(ll j=i+1;j<=n;j++) { if(j==i+1)cost[i][j]=a[j].x-a[i].x; else cost[i][j]=cost[i][j-1]+a[j].x-a[i].x; } } for(ll i=2;i<=n;i++) { ll x=a[i].x; ll w=a[i].w; dp[i][1]=1000000000000000000; dp[i][0]=1000000000000000000; dp[i][1]=min(dp[i-1][1]+w,dp[i-1][0]+w); for(ll j=i-1;j>=1;j--) { dp[i][0]=min(dp[i][0],dp[j][1]+cost[j][i]); } } printf("%I64d\n",min(dp[n][0],dp[n][1])); } }
C.因为只删除一个元素，那么我们对应维护一个前缀Gcd以及后缀Gcd即可。
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int a[150000]; int pre[150000]; int back[150000]; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(i==1)pre[i]=a[i]; else pre[i]=gcd(pre[i-1],a[i]); } for(int i=n;i>=1;i--) { if(i==n)back[i]=a[i]; else back[i]=gcd(back[i+1],a[i]); } int output=max(pre[n-1],back[2]); for(int i=2;i<=n-1;i++) { output=max(output,gcd(pre[i-1],back[i+1])); } printf("%d\n",output); } }
D.一道蛮套路的最短路相关问题，我是萌萌哒D题题解
E.
F.
G.思维题，只要从后向前扫，1的数量比2的数量多即可。
#include<stdio.h> #include<string.h> using namespace std; int a[150000]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=2;i<=n;i++) { scanf("%d",&a[i]); } if(n%2==1) { printf("No\n"); } else { int flag=0; int sum=0; for(int i=n;i>=2;i--) { if(a[i]==1)sum++; else { if(sum==0)flag=1; else sum--; } } if(flag==0)printf("Yes\n"); else printf("No\n"); } } }
H.Dp+矩阵快速幂，我是萌萌哒H题题解
I.
J.
K.
