题目 出的质量还行 失误：还是没有考虑清楚就开始写代码浪费了一些时间。优点：没有手懒 写了对拍 拍到了感觉都很稳的那种。
显然 偶数为0 考虑奇数 发现在偶数位代价为负 在奇数位 发现可行然后由于每个位置上的数字>0 答案就是奇数位的min-1
#//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define pb push_back #define un unsigned using namespace std; char *ft,*fs,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=2010; int n; int minn=INF,ans; int a[MAXN]; int b[MAXN]; int main() { //freopen("1.in","r",stdin); freopen("thief.in","r",stdin); freopen("thief.out","w",stdout); n=read(); for(int i=1;i<=n;++i)a[i]=read(); if(n&1) { for(int i=1;i<=n;++i) if(i&1)minn=min(minn,a[i]-1); /*for(int i=1;i<=n;++i) { if(i&1)b[i]=a[i]-minn; else b[i]=a[i]+minn; ans+=a[i]-b[i]; }*/ printf("%d\n",minn); } else puts("0"); return 0; } /* #//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define pb push_back #define un unsigned using namespace std; char *ft,*fs,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=2010; int n; int minn=INF,ans; int a[MAXN]; int b[MAXN]; inline int check(int x,int w) { b[x]=a[x]-w; int j=x-1,s=w; while(j) { b[j]=a[j]+s; s=-s; if(b[j]<1)return 0; --j; } j=x+1;s=w; while(j<=n) { b[j]=a[j]+s; s=-s; if(b[j]<1)return 0; ++j; } int cnt=0; for(int i=1;i<=n;++i) cnt+=a[i]-b[i]; return cnt==w; } inline void dfs() { for(int i=1;i<=n;++i) { for(int j=1;j<a[i];++j) { if(check(i,j))ans=max(ans,j); } } } int main() { freopen("1.in","r",stdin); n=read(); for(int i=1;i<=n;++i)a[i]=read(); dfs(); printf("%d\n",ans); return 0; } */
还附暴力程序...
这道题我想了很久很久 先写了一个暴力dp 还是探索不出什么大的性质感觉非常不可做因为 第一个数字总是存在限制 中间的也是。
所以局部贪心很难推广到全局最优解 所以应该考虑每个位置上的数字如何才能满足要求？采用构造设bi=ai-i 如果某一个位置上的数字为负值那么这个数字必然要修改。
这时我们发现我们对于修改一个数字就完全没有限制了直接修改成0 就一定可行因为这里是必然有空位的。所以我们只需要知道这个序列有多少个不用动即可。
那么其实最长上升不下降子序列其实就有了 二分优化一下即可。
//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define pb push_back #define un unsigned using namespace std; char *ft,*fs,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } //将一个序列中的数字修改成严格单调递增的序列 显然是构造题 const int MAXN=50010,maxn=5010; int T,n,top; int s[MAXN]; int a[MAXN],f[MAXN]; inline void calc(int x) { int l=1,r=top; while(l+1<r) { int mid=(l+r)>>1; if(s[mid]>x)r=mid; else l=mid; } if(s[l]>x)s[l]=x; else s[r]=x; } int main() { freopen("noname.in","r",stdin); freopen("noname.out","w",stdout); //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); T=read(); while(T--) { n=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<=n;++i)f[i]=a[i]-i; s[top=1]=0; for(int i=1;i<=n;++i) { if(f[i]<0)continue; if(f[i]>=s[top])s[++top]=f[i]; else calc(f[i]); } --top; printf("%d\n",n-top); } return 0; } /* //#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define pb push_back #define un unsigned using namespace std; char *ft,*fs,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } //将一个序列中的数字修改成严格单调递增的序列 显然是构造题 //但是我不会 const int MAXN=50010,maxn=5010; int T,n,top,m,ans,maxx; int f[maxn][maxn]; int a[MAXN],b[MAXN],c[MAXN]; int main() { freopen("noname.in","r",stdin); freopen("noname.out","w",stdout); //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); T=read(); while(T--) { n=read();maxx=0; for(int i=1;i<=n;++i)c[i]=a[i]=read(),maxx=max(maxx,a[i]); //if(n<=50) { m=max(n*2,maxx*2); for(int i=1;i<=n;++i) for(int j=0;j<=m;++j) f[i][j]=INF; for(int i=0;i<=m;++i)f[0][i]=0; for(int i=1;i<=n;++i) for(int j=i;j<=m;++j) { for(int k=0;k<j;++k) { f[i][j]=min(f[i][j],f[i-1][k]+(a[i]==j?0:1)); } } ans=INF; for(int i=0;i<=m;++i)ans=min(ans,f[n][i]); printf("%d\n",ans); } } return 0; } */
这题就比较水了显然是floyd一下然后状态也非常的好列 需要注意的是我们不需要记录第三个服务员的位置因为上一个位置就是第三个服务员的位置。
这样就可以通过这道题了...
#//#include<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 1000000000 #define ll long long #define db double #define pb push_back #define un unsigned using namespace std; char *ft,*fs,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=210,maxn=520; int n,T,m,ans,last; int a[MAXN][MAXN]; int b[maxn]; int f[maxn][MAXN][MAXN];//f[i][j][k]表示前i个任务且在第i个任务有一个服务员在j另一个服务员在k的最小代价。 int main() { //freopen("1.in","r",stdin); freopen("service.in","r",stdin); freopen("service.out","w",stdout); T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=read(); for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=min(a[i][j],a[i][k]+a[k][j]); for(int i=1;i<=m;++i)b[i]=read(); memset(f,0x3f,sizeof(f)); last=3;f[0][1][2]=0; for(int i=1;i<=m;++i) { //int w=INF; for(int j=1;j<=n;++j)//枚举一个服务员的位置 { for(int k=1;k<=n;++k)//枚举另一个服务员的位置 { //第一个服务员过去 f[i][last][k]=min(f[i][last][k],f[i-1][j][k]+a[j][b[i]]); //第二个服务员过去 f[i][j][last]=min(f[i][j][last],f[i-1][j][k]+a[k][b[i]]); //第三个服务员过去 f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+a[last][b[i]]); //w=min(w,f[i][j][k]); } } //cout<<w<<endl; last=b[i]; } ans=INF; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)ans=min(ans,f[m][i][j]); printf("%d\n",ans); } return 0; }
青青子佩 悠悠我思