Problem A 一眼就可以看出来是DP咯。设f[i][j]表示当走到第i行第j列时可以取得的西瓜个数最大值，则//这里的k只是循环变量，和输入的k不同 对于50%的数据，使用上面三重循环的算法直接暴力，如果不会那我也没办法。 如何优化这个方法呢？仔细观察状态转移方程，不难发现每一次都要求max(f[i-1][k])，而k所在的区间每一次只移动一位，于是可以用单调队列来解，复杂度O(nm)。 但是这样还是无法AC。看到 1<=n,m<=106 的时候，同学们是不是在绞尽脑汁想O(n)或O(m)的算法？如果我把n,m的范围给到maxlongint，那AC的人反而可能会多一些。 其实这题和n,m的大小并没什么关系！当拓展到(i,j)的时候向前扫描已经拓展过的位置，看看能从上面的哪里来到当前点。如果可以到达就更新最优值，复杂度O( k2 )，满分。 不少人都想到了正确算法然而没满分233
#include<bits/stdc++.h> using namespace std; int n,m,k,t; int abs(int x){return x<0?-x:x;} struct Edge{ int x,y,val; }a[4005]; int cmp(Edge X,Edge Y){return X.x<Y.x;} int dp[4005]={0}; int main(){ scanf("%d%d%d%d",&n,&m,&k,&t); for (int i=1;i<=k;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val); sort(a+1,a+1+k,cmp); int ans=0; for (int i=1;i<=k;i++){ dp[i]=a[i].val; for (int j=1;j<i;j++) if (abs(a[i].y-a[j].y)<=t*abs(a[i].x-a[j].x)) dp[i]=max(dp[i],dp[j]+a[i].val); ans=max(ans,dp[i]); } printf("%d",ans); }Problem B 就是解二元一次方程，解法不说了。此题数据有点坑，想AC需要非常细心，考虑到每一种情况（似乎是8种窝）。 可以结合下面的标程看一看，其实这题还是挺水的，不知道为什么绝大部分人都用Pas写而且很复杂。 想要测试数据的可以私信我。
#include<bits/stdc++.h> using namespace std; int a,b,c,d,x,y; int main(){ scanf("(%d,%d)(%d,%d)",&a,&b,&c,&d); if (a==c){ printf("-1"); return 0; } printf("y="); if(b==d) printf("%d",b); else{ x=(d-b)/(c-a),y=(a*d-b*c)/(a-c); if (x==1&&y>0) printf("x+%d",y); if (x==1&&y==0) printf("x"); if (x==1&&y<0) printf("x%d",y); if (x!=1&&y>0) printf("%dx+%d",x,y); if (x!=1&&y==0) printf("%dx",x); if (x!=1&&y<0) printf("%dx%d",x,y); } }Problem C 实际上这题只要证明出能不能到达终点就可以了，因为如果可以到达，步数是可以直接计算的。于是对于输入进行模拟，靠近终点的就可以走。当然无脑暴搜也可以，此题本来就是放水的数据手打，很弱。
var x1,y1,x2,y2,x,y,i,t,ansx,ansy:longint; chx,chy,ch:char; begin readln(x1,y1); readln(x2,y2); x:=x2-x1;y:=y2-y1; if x>0 then chx:='E' else if x<0 then chx:='W'; if y>0 then chy:='N' else if y<0 then chy:='S'; readln(t); ansx:=abs(x);ansy:=abs(y); for i:=1 to t do begin readln(ch); if (ch=chx)and(ansx>0) then dec(ansx); if (ch=chy)and(ansy>0) then dec(ansy); end; if (ansx=0)and(ansy=0) then write(abs(x)+abs(y)) else write(-1); end.Problem D 状压dp。从队列头到尾DP， 状态：f[i]表示i状态下最小的出列（不一致）的个数。 比如f[1101]表示从头到尾为1/3/4种类的西瓜的最小出列个数。 设j表示种类编号，sum表示某种种类的前缀和，length表示到此已经排到的长度，则可以列出状态转移方程： 这题满分不好拿，但是70分的暴力还是不难的吧。
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1e5+5,maxm=21,INF=1e6; int a[maxn],dp[1<<maxm],sum[maxn][maxm]; int main(){ int n,m; scanf("%d%d",&n,&m); long long all=(1<<m)-1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]);a[i]--; for(int j=0;j<m;j++){ sum[i][j]=sum[i-1][j]; if(j==a[i])sum[i][j]++; } } for(int i=0;i<=all;i++)dp[i]=INF; dp[0]=0; for(int i=0;i<=all;i++){ int cost=0; for(int j=0;j<m;j++) if((1<<j)&i)cost+=sum[n][j]; for(int j=0;j<m;j++){ if((1<<j)&i)continue; int num=sum[n][j]; int r=cost+num; int l=cost; dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+(r-l-(sum[r][j]-sum[l][j]))); } } printf("%d\n",dp[(1<<m)-1]); return 0; }