usaco-1.5-总结
1.5.1
动态规划。从下往上走。
对于走到的每一个点，都为这个点，和这个点下面两个点中最大的那个点的和。
1.5.2
可以先找出所有的回文数。然后在对所有的回文数判断素数。
注意：偶数的回文数一定不是素数，因为可以被11整除。
1.5.3
可以先求出依次求出1~8位数中是素数的数，只有尾数是1，3，7，9的时候才可以是素数。
/*ID: rowanha3LANG: C++TASK: sprime*/#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>using namespace std;int num[1000000]={2,3,5,7};int shu[4]={1,3,7,9};int biao[10];int pan(int x){ int i,n; n=sqrt(x); for(i=2;i<=n;i++) { if(x%i==0)return 0; } return 1;}void dos(){ int l=0; int r=4; int s; int leap=4; int i,j,k; for(i=2;i<=8;i++) { biao[i]=leap; for(j=l,l=r;j<r;j++) { for(k=0;k<4;k++) { s=num[j]*10+shu[k]; if(pan(s))num[leap++]=s; } } r=leap; } biao[i]=leap;}int main(){ freopen("sprime.in","r",stdin); freopen("sprime.out","w",stdout); dos(); int n,i; cin>>n; for(i=biao[n];i<biao[n+1];i++) { printf("%d\n",num[i]); } fclose(stdin); fclose(stdout); return 0;}n皇后问题。
n皇后问题的经典解法，记录每个皇后的位置。