1001:排序完按照题意做即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[],k,n;
int main(){
scanf("%d%d",&n,&k);
for (int i=; i<=n; i++) scanf("%d",&a[i]);
sort(a+,a+n+);
int m=a[n-k+]-a[k];
if (m<&&m>=) printf("NO");
else if (m>){
if (m==) printf("YES\n");
else{
for (int i=; i<=floor(sqrt(m)); i++)
if (m%i==){
printf("NO\n");
printf("%d",m);
return ;
}
printf("YES\n");
}
printf("%d",m);
return ;
}else printf("NO\n%d",m);
return ;
}
1001
1002：模拟，按题意完成即可。
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int qm,bj,lw,hv,ma,n,sum;
bool gb,wt;
string bb,cc;
int main(){
cin>>n;
for (int i=; i<=n; i++){
hv=;
//cout<<i<<":";
cin>>bb;
scanf("%d%d",&qm,&bj);
getchar();
gb=getchar()=='Y'?:;
getchar();
wt=getchar()=='Y'?:;
scanf("%d",&lw);
if (qm>&&lw) hv+=;
if (qm>&&bj>) hv+=;
if (qm>) hv+=;
if (qm>&&wt) hv+=;
if (bj>&&gb) hv+=;
if (hv>ma) {
ma=hv;
cc=bb;
}
sum+=hv;
//cout<<hv<<":"<<i;
}
cout<<cc<<endl<<ma<<endl<<sum;
}
1002
1003：模拟即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main(){
int m,t,u,f,d,s=,t1=;
char a[];
scanf("%d %d %d %d %d",&m,&t,&u,&f,&d);
for(int i=;i<t;i++)
scanf("%s",&a[i]);
for(int i=;i<t;i++){
if(a[i]=='u'||a[i]=='d') s=s+u+d;
else s=s+f*;
if(s>m) break;
t1++;
}
cout<<t1<<endl;
return ;
}
1003
1004：用了奇技淫巧。。。正解应该是记忆化搜索，我的做法是排序后贪心一波。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct fff{
int x,y,n;
}a[];
int f[][],b[][],n,m,ans;
int pd(const fff &a,const fff &b){
return a.n<b.n;
}
int main(){
cin>>n>>m;
for (int i=; i<=n; i++)
for (int j=; j<=m; j++){
scanf("%d",&b[i][j]);
a[i*m-m+j].x=i;a[i*m-m+j].y=j;a[i*m-m+j].n=b[i][j];
f[i][j]=;
}
sort(a+,a+n*m+,pd);
for (int i=; i<=n*m; i++){
int x=a[i].x,y=a[i].y;
f[x+][y]=((b[x+][y]>a[i].n)&&(f[x+][y]<f[x][y]+))?f[x][y]+:f[x+][y];
f[x-][y]=((b[x-][y]>a[i].n)&&(f[x-][y]<f[x][y]+))?f[x][y]+:f[x-][y];
f[x][y+]=((b[x][y+]>a[i].n)&&(f[x][y+]<f[x][y]+))?f[x][y]+:f[x][y+];
f[x][y-]=((b[x][y-]>a[i].n)&&(f[x][y-]<f[x][y]+))?f[x][y]+:f[x][y-];
}
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
ans=max(ans,f[i][j]);
cout<<ans;
}
1004
1005：裸01背包。。。。
#include<cstdio>
#include<iostream>
using namespace std;
int f[],p[],a[],n,v;
int main(){
cin>>v>>n;
for (int i=; i<=n; i++) scanf("%d%d",&a[i],&p[i]);
for (int i=; i<=n; i++)
for (int j=v; j>=a[i]; j--)
f[j]=max(f[j],p[i]+f[j-a[i]]);
cout<<f[v];
}
1005
1006：模拟。
#include<cstdio>
#include<iostream>
#define k(x,y) y*(a[x]-48)
using namespace std;
int main(){
char a[];
gets(a);
if ((k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,))%==(a[]=='X'?:a[]-)) cout<<"Right";
else{
cout<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[]<<a[];
if ((k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,))%==) cout<<"X";
else cout<<(k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,)+k(,))%;
}
}
1006
1007：各种排序。。。然后就行了
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int m,n,k,l,d,x,xx,yy,y;
struct fff{
int k,no;
}anh[],anl[];
int fuck(const fff &a,const fff &b){
return a.k>b.k;
}
int fuck233(const fff &a,const fff &b){
return a.no<b.no;
}
int main(){
cin>>m>>n>>k>>l>>d;
for (int i=; i<n; i++) anl[i].no=i;
for (int i=; i<m; i++) anh[i].no=i;
for (int i=; i<=d; i++){
scanf("%d%d%d%d",&x,&y,&xx,&yy);
if (x==xx) anl[min(y,yy)].k++;
else if (y==yy) anh[min(x,xx)].k++;
}
sort(anl+,anl+n+,fuck);
sort(anh+,anh++m,fuck);
sort(anl+,anl+l+,fuck233);
sort(anh+,anh+k+,fuck233);
for (int i=; i<k; i++) printf ("%d ",anh[i].no);
cout<<anh[k].no<<endl;
for (int i=; i<l; i++) printf ("%d ",anl[i].no);
cout<<anl[l].no;
}
1007
1008：又是模拟。。。
#include<iostream>
#include<cstdio>
using namespace std;
int f[][],m,n;
int main(){
scanf("%d%d",&n,&m);
f[][]=;
for (int i=; i<=m; i++)
for (int j=; j<=n; j++){
f[i][j]=f[i-][j==?n:j-]+f[i-][j==n?:j+];
}
cout<<f[m][];
}
1008
1009：略过略过~
1010：模拟即可。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
char a[];
int f[],ma,mi=0x7f;
int main(){
gets(a);
for (int i=; i<strlen(a); i++)
f[a[i]-]++;
for (int i=; i<=; i++){
ma=max(ma,f[i]);
mi=min(mi,f[i]==?0x7f:f[i]);
}
ma-=mi;
if (ma<){
cout<<"No Answer\n0";
return ;
}
else{
if (ma!=) for (int i=; i<=floor(sqrt(ma)); i++) if (ma%i==){
cout<<"No Answer\n0";
return ;
}
cout<<"Lucky Word\n"<<ma;
}
}
1010
1011：题意就是从(1,1)->(m,n)找两条最大权值不相交路线。f[i,j]就是找到了第i个人，第一条路线在第j行，第二条路线在第k行的最优值。DP一下就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
using namespace std;
int f[][][],a[][],n,m;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),m=in();
For(i,,n)
For(j,,m)
a[i][j]=in();
For(i,,n+m)
For(j,,min(n,i))
For(k,,min(n,i))
if (j!=k||i==n+m)
f[i][j][k]=max(f[i-][j-][k-],max(max(f[i-][j][k],f[i][j][k]),max(f[i-][j-][k],f[i-][j][k-])))+a[j][i-j+]+a[k][i-k+];
printf("%d\n",f[n+m][n][n]);
}
1011
1012：按题意枚举之后判断就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int n,a[]={,,,,,,,,,};
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int get(int x){
if (!x) return ;
int cnt=;
while(x){
cnt+=a[x%];
x/=;
}
return cnt;
}
int main(){
n=in();
n-=;
int ans=;
For(i,,)
For(j,i,)
if (get(i)+get(j)+get(i+j)==n)
if (i!=j) ans+=;
else ans++;
printf("%d",ans);
}
1012
1013:二维费用的01背包。我们用f[i][j]表示剩余i金j金币时能跑到zxy妹子的最多个数，记录此时的最小时间消耗为g[i][j](你泡妹子还那么急真是不懂得享受┑(￣Д ￣)┍)状态转移方程略。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
struct zxy{
int rp,c,t;
}a[];
int f[][],g[][],n,rp,m,ans,mi;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
For(i,,n)
a[i].c=in(),a[i].rp=in(),a[i].t=in();
m=in(),rp=in();
mem(g,/); g[][]=;
For(i,,n)
Ford(j,m,a[i].c)
Ford(k,rp,a[i].rp)
if (f[j-a[i].c][k-a[i].rp]+>f[j][k]||(f[j-a[i].c][k-a[i].rp]+==f[j][k]&&g[j][k]>g[j-a[i].c][k-a[i].rp]+a[i].t)){
f[j][k]=f[j-a[i].c][k-a[i].rp]+;
g[j][k]=g[j-a[i].c][k-a[i].rp]+a[i].t;
if (f[j][k]>ans||(f[j][k]==ans&&g[j][k]<mi)){
ans=f[j][k];
mi=g[j][k];
}
}
printf("%d",mi);
}
1013
1014:区间DP，枚举区间内要拿走的牌按题意完成即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int n,a[],f[][];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int l,int r){
if (f[l][r]!=f[][]) return f[l][r];
if (l+==r) return ;
For(i,l+,r-)
f[l][r]=min(f[l][r],dp(l,i)+dp(i,r)+a[l]*a[i]*a[r]);
return f[l][r];
}
int main(){
n=in();
For(i,,n) a[i]=in();
mem(f,/);
dp(,n);
printf("%d",f[][n]);
}
1014
1015：非常水的DP。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[],n,f[];
int main(){
memset(a,/,sizeof(a));
for (int i=; i<=; i++)
scanf("%d",&f[i]);
cin>>n;
a[]=;
for (int i=; i<=n+; i++)
for (int j=; j<=; j++)
a[i]=min(a[i],a[i-j]+f[j]);
cout<<a[n+];
}
1015
1016：裸01背包+1
#include<cstdio>
#include<iostream>
using namespace std;
int f[],a[],n,v;
int main(){
cin>>v>>n;
for (int i=; i<=n; i++) scanf("%d",&a[i]);
for (int i=; i<=n; i++)
for (int j=v; j>=a[i]; j--)
f[j]=max(f[j],a[i]+f[j-a[i]]);
cout<<v-f[v];
}
1016
1017：并查集之后统计没有用的合并次数即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int fa[],n,m,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int find(int x){
fa[x]=fa[x]==x?x:find(fa[x]);
return fa[x];
}
int main(){
n=in(); m=in();
For(i,,m) fa[i]=i;
For(i,,n){
int x=in(),y=in();
if (find(x)==find(y)) ans++;
else fa[find(x)]=find(y);
}
printf("%d",ans);
}
1017
1018:20！用LL就可以存了。。。。然后按题意模拟一下即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int n,k,mo=,a[];
ll ans=;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();k=in();
bool p=;
For(i,,k) mo*=;
For(i,,n)
ans*=i;
while(ans%==) ans/=;
int cnt=;
while(ans){
a[++cnt]=ans%;
ans/=;
}
Ford(i,min(cnt,k),) printf("%d",a[i]);
}
1018
1019：通过进行数学推导，我们容易发现，对于b[i] 中大于a[i]的数，用它们任意进行相减的和是一定的，反之亦然，于是我们只需要将b数组与a数组按大小一一匹配即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int a[],b[],n,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
For(i,,n) a[i]=in();
For(i,,n) b[i]=in();
sort(a+,a+n+);
sort(b+,b+n+,greater<int>());
For(i,,n)
ans+=abs(b[i]-a[i]);
printf("%d",ans);
}
1019
1020：筛法筛质数，然后对于每个a[i]暴力枚举注意及时剪枝就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
bool f[];
int pr[],ma,maxx,n,x,cnt;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
void init(){
f[]=;
For(i,,)
if (!f[i])
For(j,,/i)
f[i*j]=;
For(i,,)
if (!f[i])
pr[++cnt]=i;
return;
}
int main(){
init();
n=in();
For(i,,n){
x=in();
Ford(i,cnt,)
if (pr[i]<maxx) break;
else if (x%pr[i]==){
ma=x;
maxx=pr[i];
}
}
printf("%d",ma);
}
1020
1021:模拟即可。。。。
1021
1022：进制转换你不会吗？（从低位向上除，判断是否是奇数即可）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
ll x;
bool ans[];
inline ll in(){
ll x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
x=in();
ll p=;
int i=;
for(p=; i<=; p*=(-),i++)
if ((x/p)&){
ans[i]=;
x-=p;
}
while(!ans[i]&&i) i--;
Ford(j,i,)
printf("%d",(ans[j]?:));
}
1022
1023:简单DP，用f[i][j]表示第i分钟时疲倦值为j的最大距离，则f[i][j]=f[i-1][j-1]+d[i](1<=j<=m),f[i][0]=max(f[i-1][0],f[i-j][j])(1<=j<=i&&j<=m)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int d[],n,m,f[][];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),m=in();
For(i,,n) d[i]=in();
For(i,,n){
f[i][]=f[i-][];
For(j,,min(i,m)) f[i][]=max(f[i][],f[i-j][j]);
For(j,,m) f[i][j]=f[i-][j-]+d[i];
}
printf("%d",f[n][]);
}
1023
1024:最长不下降子序列还是很简单的吧。。。注意一下输入的处理就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int dy[],a[],f[],cnt,ans[];
char zxy[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int doit(int n){
mem(f,);
f[]=;
int ans=;
For(i,,n)
For(j,,i-)
if (a[i]>=a[j]){
f[i]=max(f[i],f[j]+);
ans=max(f[i],ans);
}
return ans;
}
int main(){
scanf("%s",zxy);
For(i,,strlen(zxy)-)
dy[zxy[i]-'a']=i;
while(scanf("%s",zxy+)!=EOF){
cnt=;
For(i,,strlen(zxy)-)
a[++cnt]=dy[zxy[i]-'a'];
printf("%d",doit(cnt));
}
}
1024
1025：判断奇偶性你不会吗？
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char a[],b;
int n;
int main(){
cin>>n;
getchar();
for (int i=; i<=n; i++){
gets(a);
b=a[strlen(a)-];
if (b%==) cout<<"even\n";
else cout<<"odd\n";
}
}
1025
1026:数据范围这么小，打暴力不就好了。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
bool f[][];
int n,m,I,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),m=in(),I=in();
int x,xx,y,yy;
For(i,,I){
x=in(),y=in(),xx=in(),yy=in();
For(i,x,xx)
For(j,y,yy)
f[i][j]=;
}
For(i,,n)
For(j,,m)
if (f[i][j]) ans++;
printf("%d",ans);
}
1026
1027：按照题意搜索即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
int a[][],dx[]={,,-,},dy[]={,,,-},n,m;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int bfs(){
int x=,y=;
int ans=a[][];
a[][]=;
while(x!=n||y!=m){
int ma=,nx,ny;
For(i,,)
if (a[x+dx[i]][y+dy[i]]>ma){
ma=a[x+dx[i]][y+dy[i]];
nx=x+dx[i],ny=y+dy[i];
}
ans+=ma;
x=nx,y=ny;
a[x][y]=;
}
return ans;
}
int main(){
n=in(),m=in();
For(i,,n)
For(j,,m)
a[i][j]=in();
printf("%d",bfs());
}
1027
1028：又一次的01背包。。
#include<cstdio>
#include<iostream>
using namespace std;
int f[],a[],n,v;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
v=in(),n=in();
for (int i=; i<=n; i++) a[i]=in();
for (int i=; i<=n; i++)
for (int j=v; j>=a[i]; j--)
f[j]=max(f[j],a[i]+f[j-a[i]]);
printf("%d",f[v]);
}
1028
1029：暴力枚举答案检查就行了吧（你要无聊加个二分也行= =）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
string a,b;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
bool check(string a,string b,int l){
For(i,,l-)
if (a[i]!=b[b.size()-l+i]) return ;
return ;
}
int main(){
cin>>a;cin>>b;
Ford(i,min(a.size(),b.size()),)
if (check(a,b,i)||check(b,a,i)){
printf("%d",i);
break;
}
}
1029
1030：BFS经典题
#include<cstdio>
#include<iostream>
using namespace std;
struct fff{
int nn,x,y;
}a[];
int dx[]={,,-,,-,,-,,},dy[]={,,,,,-,-,,-},h,t,n,m,x,y;
char aa[];
bool b[][];
int main(){
cin>>n>>m>>y>>x;
for (int i=m; i>=; i--){
cin>>aa;
for (int j=; j<n; j++)
b[i][j+]=aa[j]=='.'?:;
}
h=,t=;
a[].x=x;
a[].y=y;
a[].nn=;
b[x][y]=;
do{
h++;
for (int i=; i<=; i++){
x=a[h].x+dx[i];
y=a[h].y+dy[i];
if (x>&&x<=m&&y>&&y<=n&&!b[x][y]){
t++;
a[t].nn=a[h].nn+;
a[t].x=x;
a[t].y=y;
b[x][y]=;
}
}
}while(h<t);
cout<<a[t].nn;
}
1030
1031:典型最短路，我用的是SPFA：）
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dis[],n,m,s,e,x,y,z,a[][][],pp[],h,t;
bool b[];
int main(){
cin>>n>>m>>s>>e;
for (int i=; i<=m; i++){
scanf("%d%d%d",&x,&y,&z);
a[x][++a[x][][]][]=z;
a[x][a[x][][]][]=y;
a[y][++a[y][][]][]=z;
a[y][a[y][][]][]=x;
}
h=,t=;
pp[]=s;
b[s]=; memset(dis,/,sizeof(dis));
dis[s]=;
do{
h++;
for (int i=; i<=a[pp[h]][][]; i++)
if (dis[a[pp[h]][i][]]>dis[pp[h]]+a[pp[h]][i][]){
dis[a[pp[h]][i][]]=dis[pp[h]]+a[pp[h]][i][];
if (!b[a[pp[h]][i][]]){
t++;
pp[t]=a[pp[h]][i][];
b[a[pp[h]][i][]]=;
}
}
b[pp[h]]=;
}while(h<t);
cout<<dis[e];
}
1031
1032:由于大面额的钱币是小面额的倍数，我们容易想到一个贪心思路：先拿大面额凑，再拿小面额凑，最后注意一下钱不够和最大面额大于所需支付工资的情况即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
struct zxy{
int n,v;
}a[];
int n,v,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
bool cmp(zxy a,zxy b){
return a.v<b.v;
}
int main(){
n=in(),v=in();
For(i,,n)
a[i].v=in(),a[i].n=in();
sort(a+,a+n+,cmp);
Ford(i,n,)
if(a[i].v>v){
n--;
ans+=a[i].n;
}
while(){
int nt=;
Ford(i,n,)
while(a[i].v+nt<v&&a[i].n)
nt+=a[i].v,a[i].n--;
For(i,,n)
if(a[i].n){
nt+=a[i].v;
a[i].n--;
break;
}
if (nt<v) break;
ans++;
}
printf("%d",ans);
}
1032
1033：题意就是叫你求一颗二叉树的深度，DP或者dfs一下就行了，时间效率O（n）。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
using namespace std;
struct zxy{
int lc,rc,deep;
}a[];
int n;
int dfs(int k){
a[a[k].lc].deep=a[a[k].rc].deep=a[k].deep+;
if (!a[k].lc&&!a[k].rc) return a[k].deep;
if (!a[k].rc) return dfs(a[k].lc);
if (!a[k].lc) return dfs(a[k].rc);
return max(dfs(a[k].lc),dfs(a[k].rc));
}
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
int x,y,z;
For(i,,n-){
x=in(),y=in(),z=in();
a[x].lc=y,a[x].rc=z;
}
a[].deep=;
printf("%d",dfs());
}
1033
1034：按题意DP或者打个最短路就行了（最短路待更新），DP按题意做就好
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int f[],c[],s[],n,k;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),k=in();
For(i,,k) s[i]=in(),c[i]=in();
For(i,,n) f[i]=-INF;
For(i,,n){
bool b=;
For(j,,k)
if (s[j]==i){
f[i+c[j]]=max(f[i+c[j]],f[i]);
b=;
}
if (!b) f[i+]=max(f[i+],f[i]+);
}
printf("%d",f[n+]);
}
1034DP
1035：原谅本人过蒻并不会二分图匹配。。。（容我以后填坑）
1036：排序以后处理一下即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int n,a[],b[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
For(i,,n) a[i]=in();
sort(a+,a+n+);
int cnt=;
For(i,,n)
if (a[i]!=a[i-]){
printf("%d %d\n",a[i-],cnt);
cnt=;
}
else ++cnt;
printf("%d %d",a[n],cnt);
}
1036
1037：高精乘法维护抹零后的后20位即可，其余同1018
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
struct zxy{
int begin,l,v[];
zxy(){
begin=,l=;
v[]=;
}
void friend operator *(zxy &a,int b){
For(i,a.begin,min(a.begin+,a.l))
a.v[i]*=b;
For(i,a.begin,min(a.begin+,a.l)){
a.v[i+]+=a.v[i]/;
a.v[i]%=;
if(a.v[a.l+])a.l++;
while(!a.v[a.begin])a.begin++;
}
}
}ans;
int n,k;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),k=in();
For(i,,n) ans*i;
Ford(i,ans.begin+k-,ans.begin)
printf("%d",ans.v[i]);
}
1037
1038：线段树裸题（大神可以用RMQ，本人太蒻）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
#define mid ((l+r)>>1)
using namespace std;
struct zxy{
int mi;
}tr[];
int n,q;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline void update(int l,int r,int k,int t,int add){
if (l==r) {
tr[k].mi=add;
return;
}
if (t<=mid) update(l,mid,k<<,t,add);
else update(mid+,r,k<<|,t,add);
tr[k].mi=min(tr[k<<].mi,tr[k<<|].mi);
return;
}
inline int query(int l,int r,int a,int b,int k){
if (a==l&&b==r) return tr[k].mi;
if (b<=mid) return query(l,mid,a,b,k<<);
if (a>mid) return query(mid+,r,a,b,k<<|);
return min(query(l,mid,a,mid,k<<),query(mid+,r,mid+,b,k<<|));
}
int main(){
n=in(),q=in();
For(i,,n) update(,n,,i,in());
For(i,,q){
int x=in(),y=in();
printf("%d ",query(,n,x,y,));
}
}
1038
1039：线段树裸题+1
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
#define mid ((l+r)>>1)
using namespace std;
struct zxy{
int mi;
}tr[];
int n,q;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline void update(int l,int r,int k,int t,int add){
if (l==r) {
tr[k].mi=add;
return;
}
if (t<=mid) update(l,mid,k<<,t,add);
else update(mid+,r,k<<|,t,add);
tr[k].mi=min(tr[k<<].mi,tr[k<<|].mi);
return;
}
inline int query(int l,int r,int a,int b,int k){
if (a==l&&b==r) return tr[k].mi;
if (b<=mid) return query(l,mid,a,b,k<<);
if (a>mid) return query(mid+,r,a,b,k<<|);
return min(query(l,mid,a,mid,k<<),query(mid+,r,mid+,b,k<<|));
}
int main(){
n=in(),q=in();
For(i,,n) update(,n,,i,in());
For(i,,q){
int k=in(),x=in(),y=in();
if (!(k^))
printf("%d ",query(,n,x,y,));
else update(,n,,x,y);
}
}
1039
1040&1041：裸的高精加减法，注意一下字符串处理的一些细节即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
struct data{
int l,v[];
void clear(){
l=;
mem(v,);
}
data friend operator +(data a,data b){
data c;c.clear();
c.l=max(a.l,b.l);
For(i,,c.l) c.v[i]=a.v[i]+b.v[i];
For(i,,c.l) c.v[i+]+=c.v[i]/,c.v[i]%=;
if (c.v[c.l+]) ++c.l;
return c;
}
data friend operator -(data a,data b){
data c;c.clear();
c.l=a.l;
For(i,,c.l)
if (a.v[i]>=b.v[i])
c.v[i]=a.v[i]-b.v[i];
else {
a.v[i+]--;
c.v[i]=a.v[i]+-b.v[i];
}
while(!c.v[c.l]&&c.l) c.l--;
return c;
}
}ans,tmp[];
char a[],ch[];
int cnt;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
scanf("%s",a);
cnt=;
Ford(i,strlen(a)-,)
if (a[i]!='+'&&a[i]!='-') tmp[cnt].v[++tmp[cnt].l]=a[i]-'';
else ch[cnt++]=a[i];
ans=tmp[cnt];
Ford(i,cnt-,)
if (ch[i]=='+') ans=ans+tmp[i]; else ans=ans-tmp[i];
Ford(i,ans.l,) printf("%d",ans.v[i]);
}
1041&1042
1042&1043：栈的练习。。。。注意处理细节。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<stack>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
stack<ll> num;
stack<char> ch;
string s;
int cnt;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int inline getlevel(char x){
if (x=='+'||x=='-') return ;
if (x=='*'||x=='/') return ;
if (x=='^') return ;
if (x=='(') return ;
if (x=='#') return -INF;
return -;
}
ll calc(){
char tmp=ch.top();ch.pop();
ll b=num.top();num.pop();
ll a=num.top();num.pop();
if(tmp=='+')return a+b;
if(tmp=='-')return a-b;
if(tmp=='*')return a*b;
if(tmp=='/')return a/b;
ll ans=;
for(int i=;i<=b;i++)
ans*=a;
return ans;
}
int main(){
cin>>s;
For(i,,s.size()-)
if (s[i]=='(') cnt++;
else if (s[i]==')') --cnt;
while(cnt>) cnt--,s=s+")";
while(cnt<) cnt++,s="("+s;
s=s+"#";
ch.push('#');
num.push();
int i=;
while(s[i]!='#'||ch.top()!='#'){
if (s[i]<''||s[i]>''){
if(getlevel(s[i])>getlevel(ch.top())){
s[i]=s[i]=='('?'[':s[i];
ch.push(s[i]);i++;
}
else
if (ch.top()=='[') ch.pop(),i++;
else num.push(calc());
}
else{
ll x=;
while(s[i]>=''&&s[i]<='') x=x*+s[i++]-'';
num.push(x);
}
}
cout<<num.top();
}
1042&1043
1044：递推
#include<cstdio>
#include<iostream>
#define For(i,a,b) for (int i=1; i<=a; i+=b)
#define in(a) scanf("%d",&a)
using namespace std;
int n,f[][],a[][],ans=-0x7ffffff;
int main(){
in(n);
For(i,n,)
For(j,i,)
in(a[i][j]);
f[][]=a[][];
for (int i=; i<=n; i++)
For(j,i,){
f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
}
For(i,n,) ans=max(ans,f[n][i]);
cout<<ans;
}
1044
1045：区间DP，f[i][j][k]表示在[i,j]内用了k个乘号,f[l][r][k]=max(f[l][i][j]+f[i+1][r][k-j],f[l][i][j]*f[i+1][r][k-j-1])(1<=l,r<=n;l<=i<r;0<=j<=k;注意非法情况的剪枝，以及r-l=k的情况）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int f[][][],a[],n,num;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int l,int r,int k){
if (r<l||r-l<k||k<) return -;
if (f[l][r][k]>) return f[l][r][k];
if (r-l==k){
f[l][r][k]=;
For(i,l,r)
f[l][r][k]*=a[i];
return f[l][r][k];
}
For(i,l,r-)
For(j,,k)
f[l][r][k]=max(f[l][r][k],max(dp(l,i,j)+dp(i+,r,k-j),dp(l,i,j)*dp(i+,r,k-j-)));
return f[l][r][k];
}
int main(){
n=in(),num=in();
mem(f,(-));
For(i,,n) f[i][i][]=a[i]=in();
printf("%d",dp(,n,num));
}
1045
1046:DP,用f[i][j]表示a串排了i个，b串拍了j个，状态转移方程是f[i][j]=min(f[i-1][j-1]+abs(a[i-1]-b[j-1]),min(f[i-1][j]+k,f[i][j-1]+k))，边界条件是f[i][0]=i*k,f[0][j]=j*k。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
#define MAXN 2001
using namespace std;
int f[MAXN][MAXN],n,m,k;
char a[MAXN],b[MAXN];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int dp(){
mem(f,/);
f[][]=;
For(i,,n) f[i][]=i*k;
For(i,,m) f[][i]=i*k;
For(i,,n)
For(j,,m)
f[i][j]=min(f[i-][j-]+abs(a[i-]-b[j-]),min(f[i-][j]+k,f[i][j-]+k));
return f[n][m];
}
int main(){
scanf("%s%s%d",a,b,&k);
n=strlen(a);
m=strlen(b);
printf("%d",dp());
}
1046
1048：我们不妨假设齐王的马是从快到小依次出的，用f[l][r]表示田忌可以从自己第l强到第r蒻的马中任选一匹在本轮出战，此时赛马已经比过了(n-r+l-1)轮,我们容易想到一个DP的状态方程式：
f[l][r]=max(f[l+1][r]+price(l,n-r+l),f[l][r-1]+price(r,n-r+l));price(i,j)表示用田忌的第i匹马和第j匹马在本轮出战能拿到的money。然后用记忆化搜索实现即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 1000000000
using namespace std;
int f[][],n,a[],b[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int price(int x,int y){
if (a[x]>b[y]) return ;
if (a[x]<b[y]) return (-);
return ;
}
inline int dp(int l,int r){
if (f[l][r]>(-INF)) return f[l][r];
if (r<l) return -INF;
if (l==r) {
f[l][r]=price(l,n);
return f[l][r];
}
f[l][r]=max(dp(l+,r)+price(l,n-r+l),dp(l,r-)+price(r,n-r+l));
return f[l][r];
}
int main(){
mem(f,-/);
n=in();
For(i,,n) a[i]=in();
For(i,,n) b[i]=in();
sort(a+,a+n+,greater<int>());
sort(b+,b+n+,greater<int>());
printf("%d",dp(,n));
}
1048
1049：裸DP题，方程式都没什么好讲的。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int f[],a[],n,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
For(i,,n) a[i]=in();
f[]=;
For(i,,n)
For(j,,i-)
if (a[i]>=a[j]){
f[i]=max(f[i],f[j]+);
ans=max(f[i],ans);
}
printf("%d",ans);
}
1049
1050：用f[i][j]表示a串前i个字符与b串前j个字符进行匹配的最长子串长度，状态转移方程式是：f[i][j]=max(f[i-1][j],f[i][j-1])(a[i]!=b[j])&f[i][j]=f[i-1][j-1]+1(a[i]=a[j]).然后用记忆化搜索实现即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int f[][];
string a,b;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int i,int j){
if (i<||j<) return ;
if (f[i][j]) return f[i][j];
if (a[i]==b[j]) return f[i][j]=dp(i-,j-)+;
return f[i][j]=max(dp(i-,j),dp(i,j-));
}
int main(){
cin>>a>>b;
printf("%d",dp(a.size()-,b.size()-));
}
1050
1051:典型的树形DP题，我们采用左儿子右兄弟法存树，f[i][j]表示第i个节点还能选j门课的最优值，枚举DP到儿子时可以选的课数l(1<=l<=j)，可以发现
f[i][j]=max(f[儿子][j-i-1]+f[兄弟][i]+i节点的权值,f[兄弟][j]);然后我们使用记忆化搜索实现树上DP即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
struct zxy{
int v,son,bra;
}tr[];
int n,f[][],m,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int k,int t){
if (!(k&&t)) return ;
if (f[k][t]) return f[k][t];
f[k][t]=tr[k].v;
For(i,,t)
f[k][t]=max(f[k][t],dp(tr[k].son,t-i)+dp(tr[k].bra,i-)+tr[k].v);
f[k][t]=max(dp(tr[k].bra,t),f[k][t]);
return f[k][t];
}
int main(){
n=in(),m=in();
For(i,,n){
int x=in(),y=in();
tr[i].bra=tr[x].son;
tr[x].son=i;
tr[i].v=y;
}
f[][]=;
tr[].v=;
printf("%d",dp(tr[].son,m));
}
1051
1052：显然又是一题树上DP，用f[i][0/1]表示取不取第i节点时的最优状态，采用了很暴力的方法存树，找到root，跑一次dfs枚举儿子累加状态即可。
状态转移方程：f[i][0]=Σmax(f[儿子][1],f[儿子][0])，f[i][1]=第i点的权值+∑f[儿子][0].
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int n,f[][],fa[];
bool b[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline void treedp(int k){
b[k]=;
For(i,,n)
if (b[i]&&fa[i]==k){
treedp(i);
f[k][]+=f[i][];
f[k][]+=max(f[i][],f[i][]);
}
}
int main(){
n=in();
For(i,,n) f[i][]=in();
For(i,,n-){
int x=in(),y=in();
fa[x]=y;
b[x]=;
}
int s;
For(i,,n) if (!b[i]){
s=i;
break;
}
treedp(s);
printf("%d",max(f[s][],f[s][]));
}
1052
1053：字符串处理，按题意做，注意连续'-'和开头以及结尾的处理就行了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (char i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i<=b; i++)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
string a;
int p1,p2,p3;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline bool digit(char k){
return k>=''&&k<='';
}
inline bool alpha(char k){
return k>='a'&&k<='z';
}
inline void get_(char a,char b){
if (b<=a||(alpha(a)&&digit(b))||(digit(a)&&alpha(b))||a=='-'||b=='-') {
putchar('-');
return;
}
int cnt=;
if (p3-){
if (p1==) For(i,a+,b-)
Ford(j,,p2)
putchar('*');
if (p1==&&alpha(a))
for(char i=b-; i>a; i--)
Ford(j,,p2)
putchar(i-'a'+'A');
if (p1==||(p1==&&digit(a))) for(char i=b-; i>a; i--)
Ford(j,,p2)
putchar(i);
return;
}
if (p1==) For(i,a+,b-)
Ford(j,,p2)
putchar('*');
if (p1==&&alpha(a))
For(i,a+,b-)
Ford(j,,p2)
putchar(i-'a'+'A');
if (p1==) For(i,a+,b-)
Ford(j,,p2)
putchar(i);
}
int main(){
p1=in(),p2=in(),p3=in();
cin>>a;
Ford(i,,a.size()-)
if (a[i]!='-'||i==) putchar(a[i]);
else get_(a[i-],a[i+]);
}
1053
1055:又是区间DP,用f[l][r]表示将[l,r]合并成一堆以后的最优值，这样的话状态转移方程式是：f[l][r]=f[l][i]+f[i+1][r]+∑(j=l,j<=r)a[j](l<=i<=r)，其中我们可以用前缀和简化∑，然后使用记忆化搜索即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 100000000
using namespace std;
int f[][],n,s[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int l,int r){
if (f[l][r]<INF) return f[l][r];
if (l==r) return ;
For(i,l,r-) f[l][r]=min(dp(l,i)+dp(i+,r)+s[r]-s[l-],f[l][r]);
return f[l][r];
}
int main(){
n=in();
For(i,,n) s[i]=s[i-]+in();
mem(f,/)
printf("%d",dp(,n));
}
1055
1056：still区间DP，首先对循环这个特性我们进行处理，用[n+1,2*n]复制与[1,n]的相同信息，这样之后从1~n都进行一次长度为n的DP取最优即可。
DP的方法：用f[l][r]表示将[l,r]合并后的最优值，状态转移方程：f[l][r]=f[l][i]+f[i+1][r]+a[l]*a[i+1]*a[r](l<=i<=r)，边界是f[i][i]=0；
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int f[][],a[],n,ans;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dp(int l,int r){
if (f[l][r]) return f[l][r];
if (l==r) return ;
For(i,l,r-) f[l][r]=max(f[l][r],dp(l,i)+dp(i+,r)+a[l]*a[i+]*a[r+]);
return f[l][r];
}
int main(){
n=in();
For(i,,n) a[i]=in();
For(i,n+,*n) a[i]=a[i-n];
For(i,,n)
ans=max(ans,dp(i,i+n-));
printf("%d",ans);
}
1056
1057：裸01背包，处理一下依附关系即可，具体参见程序。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
struct zxy{
int ls,rs,v,imp;
bool pp;
}tr[];
int n,m,f[];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
m=in(),n=in();
m/=;
For(i,,n){
tr[i].v=in();
tr[i].v/=;
tr[i].imp=in();
int y=in();
if (y){
tr[i].pp=;
if (tr[y].ls) tr[y].rs=i;
else tr[y].ls=i;
}
}
tr[].v=tr[].imp=;
For(i,,n)
if (!tr[i].pp)
Ford(j,m,tr[i].v){
int ls=tr[i].ls,rs=tr[i].rs;
if (j-tr[i].v>=tr[ls].v)
f[j]=max(f[j],f[j-tr[i].v-tr[ls].v]+tr[i].v*tr[i].imp+tr[ls].v*tr[ls].imp);
if (j-tr[i].v>=tr[rs].v)
f[j]=max(f[j],f[j-tr[i].v-tr[rs].v]+tr[i].v*tr[i].imp+tr[rs].v*tr[rs].imp);
if (j-tr[i].v>=tr[rs].v+tr[ls].v)
f[j]=max(f[j],f[j-tr[i].v-tr[rs].v-tr[ls].v]+tr[i].v*tr[i].imp+tr[rs].v*tr[rs].imp+tr[ls].v*tr[ls].imp);
f[j]=max(f[j],f[j-tr[i].v]+tr[i].v*tr[i].imp);
}
printf("%d",f[m]*);
}
1057
1058：单纯的模拟，题意自己去外面找去┑(￣Д ￣)┍
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
struct zxy{
int no,no2;
}order[];
int use[][],n,m,cnt[],t[][],mac[][],mact[],ans,end[];
bool used[][];
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline bool pd(int ma,int s,int e){
For(i,s,e)
if (used[ma][i]) return ;
return ;
}
int main(){
m=in(),n=in();
For(i,,m*n) order[i].no=in(),order[i].no2=++cnt[order[i].no];
For(i,,n)
For(j,,m) mac[i][j]=in();
For(i,,n)
For(j,,m) t[i][j]=in();
For(i,,m*n){
int gj=order[i].no,no=order[i].no2;
int tim=t[gj][no],macc=mac[gj][no];
For(j,end[gj],INF)
if (pd(macc,j,j+tim-)){
For(k,j,j+tim-)
used[macc][k]=;
end[gj]=j+tim;
if (j+tim>ans) ans=j+tim;
break;
}
}
printf("%d",ans);
}
1058
1062:题目都说了和合并方法和合并*沙子差不多，这里就不多说怎么做了，做法与1055类似，详见代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 100000000
using namespace std;
int f[][],n,s[],m;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline int dpmi(int l,int r){
if (f[l][r]<INF) return f[l][r];
if (l==r) return ;
For(i,l,r-) f[l][r]=min(dpmi(l,i)+dpmi(i+,r)+s[r]-s[l-],f[l][r]);
return f[l][r];
}
inline int dpma(int l,int r){
if (f[l][r]) return f[l][r];
if (l==r) return ;
For(i,l,r-) f[l][r]=max(dpma(l,i)+dpma(i+,r)+s[r]-s[l-],f[l][r]);
return f[l][r];
}
int main(){
n=in();m=in();
For(i,,n) s[i]=s[i-]+in();
int ma=dpma(,n);
mem(f,/);
int mi=dpmi(,n);
if (m<mi) printf("I am..Sha...X");
else if (m>ma) printf("It is easy");
else printf("I will go to play WarIII");
}
1062
1063：我们可以比较容易的想到一种贪心的方法，用头指针h和尾指针t来在数字串上模拟一个队列，对于队列判断一下是否符合条件，进行答案更新，这样的话效率还是很慢（O（mn）），我们可以考虑对队列中不同元素的数量进行一个统计，这样当cnt=m时，自然队列就符合条件，具体实现方法见代码，时间效率为O（n）。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int n,m,a[],b[],h,t;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in(),m=in();
For(i,,n) a[i]=in();
int cnt=,ans=n+;
h=,t=;
while(h<=n-m+&&t<=n){
while(cnt!=m&&t<=n)
cnt=b[a[++t]]?cnt:cnt+,b[a[t]]++;
if (t-h+<ans) ans=t-h+;
b[a[h]]--;
if (!b[a[h]]) cnt--;
h++;
}
if (ans<=n)printf("%d",ans);
else printf("NO");
}
1063
1065：纯模拟
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int n,c,x;
int main(){
for (int i=; i<=; i++){
n+=;
scanf("%d",&x);
n-=x;
if (n<){
cout<<-i;
exit();
}
c+=n/*;
n%=;
}
cout<<c+n;
}
1065
1066：STL练习题，可以采用系统优先队列，自带堆等（本人采用自带堆排）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 2000000000
using namespace std;
int heap[],hp,n,ans;
void in(int x){
heap[++hp]=x;
push_heap(heap+,heap+hp+,greater<int>());
}
int out(){
pop_heap(heap+,heap+hp+,greater<int>());
return heap[hp--];
}
int main(){
cin>>n;
for (int i=; i<=n; i++){
int x;
scanf("%d",&x);
in(x);
}
while(hp!=){
int x=out(),y=out();
ans+=(x+y);
in(x+y);
}
cout<<ans;
}
1066
1067:用DP从前往后和从后往前各求一次到每个人的最长连续上升子序列长度，这样以来选每个人作为最高点时的答案就很好求了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define Ford(i,a,b) for (int i=a; i>=b; i--)
#define File(fn) freopen(fn".in","r",stdin); freopen(fn".out","w",stdout);
#define mem(qaq,num) memset(qaq,num,sizeof(qaq));
#define ll long long
#define mod 1000000007
#define INF 700000000
using namespace std;
int upp[],n,a[],dow[],ans=0x7fffffff;
inline int in(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
int main(){
n=in();
For(i,,n) a[i]=in();
For(i,,n)
For(j,,i-)
if (a[i]>a[j])
upp[i]=max(upp[i],upp[j]+);
Ford(i,n,)
Ford(j,n+,i+)
if (a[i]>a[j])
dow[i]=max(dow[i],dow[j]+);
For(i,,n)
ans=min(ans,n-upp[i]-dow[i]+);
printf("%d",ans);
}
1067
1075：数字三角形无脑递推系列...
#include<cstdio>
#include<iostream>
#define For(i,a,b) for (int i=1; i<=a; i+=b)
#define in(a) scanf("%d",&a)
using namespace std;
int n,a[][],ans=-;bool f[][][];
int main(){
in(n);
For(i,n,)
For(j,i,)
in(a[i][j]);
f[][][a[][]%]=;
for (int i=; i<=n; i++)
For(j,i,){
for (int k=; k<=; k++) if (f[i-][j][k]) f[i][j][(k+a[i][j])%]=;
for (int k=; k<=; k++) if (f[i-][j-][k]) f[i][j][(k+a[i][j])%]=;
}
For(j,n,)
for (int i=; i>=; i--) if (f[n][j][i]) ans=max(ans,i);
cout<<ans;
}
1075
1079：数字三角形无脑递推系列...
#include<cstdio>
#include<iostream>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define in(a) scanf("%d",&a)
using namespace std;
int n,f[][],a[][],ans=-0x7ffffff;
int main(){
in(n);
For(i,,n)
For(j,,i)
in(a[i][j]);
f[][]=a[][];
For(i,,n/)
For(j,,i)
f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
For(i,,n/-) f[n/][i]=;
For(i,n/+,n)
For(j,n/,i)
f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
For(i,n/,n) ans=max(ans,f[n][i]);
cout<<ans;
}
1079
1084：数字三角形无脑递推系列...
#include<cstdio>
#include<iostream>
#define For(i,a,b) for (int i=a; i<=b; i++)
#define in(a) scanf("%d",&a)
using namespace std;
int n,f[][],a[][],ans=-0x7ffffff,x,y;
int main(){
in(n);
For(i,,n)
For(j,,i)
in(a[i][j]);
in(x);in(y);
f[][]=a[][];
For(i,,x)
For(j,,i)
f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
For(i,,x)if (i!=y) f[x][i]=-;
For(i,x+,n)
For(j,y,i)
f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
For(i,y,n) ans=max(ans,f[n][i]);
cout<<ans;
}
1084
本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:13960948839@163.com.