题目：
1.刮刮卡
已知n（n<=1000000）张刮刮卡按顺序排列,刮开可以获得B元现金和B个积分,购买刮刮卡需要A元,某人若按照顺序刮开的话··当B的总和小于A时便会停止刮卡（即花出去的钱多余赢得的钱）,现在我们可以将前k张按原来的顺序放到后面去···问k取多少时这个人可以获得多少积分？
2.矩阵
给出一个n行m阵的矩阵（n，m<=100）,问如果从中选出K个互不重叠的非空子矩阵使得子矩阵的和最大
3.裁剪表格
给出n行m列的矩阵··（n,m<=1000）和q（q<=10000）次操作··每次操作交换两个互不重合的子矩阵···输出最后的矩阵
题解：
1.最大子串和
略
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e6+;
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int num[N*],a[N],b[N*],n;
int main()
{
//freopen("rock.in","r",stdin);
//freopen("rock.out","w",stdout);
n=R();int ans=,sum1=,maxx=,sum2=;
for(int i=;i<=n;i++) b[i]=b[i+n]=R();
for(int i=;i<=n;i++) a[i]=R(),num[i]=num[i+n]=b[i]-a[i];
int Head=;
while(Head<=n)
{
if(num[Head]<) {Head++;continue;}
int Tail=Head;sum1=,sum2=;
while(Tail-Head+<=n)
{
sum1+=num[Tail];
sum2+=b[Tail];
if(sum2>maxx)
maxx=sum2,ans=Head-;
if(Tail-Head+<=n&&sum1+num[Tail+]>=)
Tail++;
else break;
}
Head=Tail+;
}
cout<<ans<<endl;
return ;
}
2.dp
用f[i][j][k]表示第一列取了前i个,第二列取了前j个且组成了k个子矩阵的最小值,具体转移方程看代码吧··
md考试时忘记初始化-inf了····下次一定要注意··
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int K=;
const long long inf=1e+;
int n,m,k,num[N],map[N][];
long long f1[N],sum[][N],temp[N],f2[N][N][K];
inline int R()
{
char c;int f=,i=;
for(c=getchar();(c<''||c>'')&&c!='-';c=getchar());
if(c=='-') i=-,c=getchar();
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f*i;
}
int main()
{
//freopen("matrix.in","r",stdin);
// freopen("matrix.out","w",stdout);
n=R(),m=R(),k=R();
if(m==)
{
for(int i=;i<=n;i++) num[i]=R();
memset(f1,-,sizeof(f1));
f1[]=;
for(int i=;i<=k;i++)
{
for(int j=i;j<=n;j++)
{
if(j==i) f1[j]=temp[j-]+num[j];
else f1[j]=max(f1[j-]+num[j],temp[j-]+num[j]);
}
for(int j=i;j<=n;j++)
{
if(j==i) temp[j]=f1[j];
else temp[j]=max(temp[j-],f1[j]);
}
}
long long ans=-inf;
for(int i=k;i<=n;i++) ans=max(ans,f1[i]);
cout<<ans<<endl;
}
else
{
memset(f2,-,sizeof(f2));
long long tot=;bool flag=true;
for(int i=;i<=n;i++)
for(int j=;j<=;j++)
{
map[i][j]=R();tot+=map[i][j];
if(map[i][j]<) flag=false;
sum[j][i]=sum[j][i-]+map[i][j];
}
if(flag)
{
cout<<tot<<endl;return ;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) f2[i][j][]=;
for(int i=;i<=k;i++)
for(int j=;j<=n;j++) //第一列
for(int l=;l<=n;l++) //第二列
{
f2[j][l][i]=max(f2[j-][l][i],f2[j][l-][i]);
for(int p=;p<j;p++)
f2[j][l][i]=max(f2[j][l][i],f2[p][l][i-]+sum[][j]-sum[][p]);
for(int p=;p<l;p++)
f2[j][l][i]=max(f2[j][l][i],f2[j][p][i-]+sum[][l]-sum[][p]);
if(l==j)
for(int p=;p<j;p++)
f2[j][l][i]=max(f2[j][l][i],f2[p][p][i-]+sum[][l]-sum[][p]+sum[][j]-sum[][p]);
}
cout<<f2[n][n][k]<<endl;
}
return ;
}
3.链表
看了题解后发现链表是一个神奇的东西··另外也发现register配上for循环的优化效果的显著···
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=;
int n,m,q,pos[N][N],ri[N*N],down[N*N],val[N*N],tot;
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
inline int find(int x,int y)
{
int t=pos[][];
for(int i=;i<=x;i++)
t=down[t];
for(int i=;i<=y;i++)
t=ri[t];
return t;
}
int main()
{
//freopen("a.in","r",stdin);
n=R(),m=R(),q=R();
for(register int i=;i<=n;i++)
for(register int j=;j<=m;j++)
val[pos[i][j]=++tot]=R();
for(register int i=;i<=m+;i++)
pos[][i]=++tot,pos[n+][i]=++tot;
for(register int i=;i<=n;i++)
pos[i][]=++tot,pos[i][m+]=tot;
for(register int i=;i<=n;i++)
for(register int j=;j<=m;j++)
{
ri[pos[i][j]]=pos[i][j+];
down[pos[i][j]]=pos[i+][j];
}
while(q--)
{
int r1=R(),c1=R(),r2=R(),c2=R(),h=R(),w=R();
register int t1=find(r1-,c1-),t2=find(r2-,c2-),T1,T2,i;
for(T1=t1,T2=t2,i=;i<=h;i++)
swap(ri[T1=down[T1]],ri[T2=down[T2]]);
for(i=;i<=w;i++)
swap(down[T1=ri[T1]],down[T2=ri[T2]]);
for(T1=t1,T2=t2,i=;i<=w;i++)
swap(down[T1=ri[T1]],down[T2=ri[T2]]);
for(i=;i<=h;i++)
swap(ri[T1=down[T1]],ri[T2=down[T2]]);
}
int p=pos[][];
for(register int i=;i<=n;i++)
{
p=down[p];
for(register int j=,t=p;j<=m;j++)
cout<<val[t=ri[t]]<<" ";
cout<<endl;
}
return ;
}