1.5.1 numtri
動态規劃入門，我也水一回。。。
#include<stdio.h>
long max(long a,long b)
{
if(a > b)return a;
else return b;
}
long a[1010][1010];
int main()
{
long i,j,n;
freopen("numtri.in","r",stdin);
freopen("numtri.out","w",stdout);
scanf("%ld",&n);
for(i = 1;i <= n;i ++)
for(j = 1;j <= i;j ++)
scanf("%ld",&a[i][j]);
for(i = n-1;i >= 1;i --)
for(j = 1;j <= i;j ++)
a[i][j] += max(a[i+1][j],a[i+1][j+1]);
printf("%ld\n",a[1][1]);
return 0;
}
1.5.2 pprime
素數+回文，由于題目所給的範圍太大，是以第一次寫時果不其然輕松逾時。 第二次又換了種想法，原本想用埃氏篩選，再判斷回文，目測了一下，有點怕逾時，沒想到寫完送出直接 就超出空間範圍了。。。 于是，選擇了打表，唉！
#include <fstream>
using namespace std;
const int N = 781;
int p[1000] = {0,2,3,5,7,
11,
101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,
10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,
14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,
19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,
34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,
70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,
76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,
93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,
1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,
1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,
1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,
1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,
1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,
1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,
1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,
1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,
1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,
1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,
1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,
1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,
1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,
1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,
1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,
1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,
1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,
1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,
3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,
3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,
3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,
3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,
3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,
3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,
3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,
3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,
3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,
3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,
3708073,3709073,3716173,3717173,3721273,3722273,
3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,
3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,
3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,
3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,
3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,
7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,
7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,
7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,
7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,
7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,
7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,
7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,
7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,
7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,
7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,
7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,
7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,
7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,
7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,
9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,
9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,
9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,
9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,
9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,
9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,
9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,
9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,
9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,
9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,
9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,
9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,
9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,
9981899,9989899};
int a , b , i , j;
int main()
{
ifstream cin("pprime.in");
ofstream cout("pprime.out");
cin >> a >> b;
for (i = 1 ; i <= 781 ; i++)
if (p[i] >= a) break;
for (j = 781 ; j >= i ; j--)
if (p[j] <= b) break;
for (int k = i ; k <= j ; k++)
cout << p[k] << endl;
return 0;
}
1.5.3 sprime
繼續dfs
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n;
int check(int a)
{
if(a == 1)
return 0;
if(a == 2)
return 1;
int i,e;
e = (int)sqrt(a);
for(i = 2; i <= e; i ++)
if(a % i == 0)
return 0;
return 1;
}
void dfs(int num,int deep)
{
if(deep > n)
return;
if(check(num))
if(deep == n)
printf("%d\n",num);
else
{
dfs(num*10+1,deep+1);
dfs(num*10+3,deep+1);
dfs(num*10+5,deep+1);
dfs(num*10+7,deep+1);
dfs(num*10+9,deep+1);
}
}
int main()
{
freopen("sprime.in","r",stdin);
freopen("sprime.out","w",stdout);
scanf("%d",&n);
dfs(1,1);
dfs(2,1);
dfs(3,1);
dfs(4,1);
dfs(5,1);
dfs(6,1);
dfs(7,1);
dfs(8,1);
dfs(9,1);
return 0;
}
1.5.4 checker
N皇後問題，深搜處理（感覺自己搜尋學的真的不好），貼一下白書上的代碼
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("checker.in");
ofstream fout("checker.out");
int n,ans,k,c[15],vis[30][30];
void search(int cur)
{
int i;
if(cur==n) //遞歸邊界，如果走到這裡，所有皇後必然不沖突
{
ans++;
if(k<3) //列印前三組
{
fout<<c[0]+1;
for(int i=1;i!=n;i++)
fout<<" "<<c[i]+1;
fout<<endl;
k++;
}
}
else
for(i=0;i<n;i++)
{
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])//直接利用二維數組判斷
{
c[cur]=i;
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1; //修改全局變量
search(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0; //将全局變量的值改回來
}
}
}
int main()
{
fin>>n;
memset(c,0,sizeof(c));
search(0);
fout<<ans<<endl;
return 0;
}
USACO中牽扯到了動規問題，譬如有關最長公共子序列的問題 Common Subsequence
| Time Limit: 1000MS | Memory Limit: 10000K |
| Total Submissions: 35803 | Accepted: 14272 |
Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
Input
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
Output
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
貼一份題解，思路很清晰：
#include <iostream>
#include <string>
using namespace std;
const int SIZE = 999;
int dp[SIZE][SIZE] = {0};
int max(int x, int y)
{
return x > y ? x : y;
}
int main()
{
int len1, len2;
string str1, str2;
while (cin >> str1 >> str2)
{
len1 = str1.length();
len2 = str2.length();
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (str1[i-1] == str2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << dp[len1][len2] << endl;
}
return 0;
}
也順便水一下最長上升子序列問題吧
最長上升子序列問題：
給出一個由n個數組成的序列x[1..n]，找出它的最長單調上升子序列。即求最大的m和a1,
a2……,am，使得a1<a2<……<am且x[a1]<x[a2]<……<x[am]。
動态規劃求解思路分析：（O(n^2)）
經典的O(n^2)的動态規劃算法，設A[i]表示序列中的第i個數，F[i]表示從1到i這一段中以i結尾的最長上升子序列的長度，初始時設F[i] = 0(i = 1, 2, ..., len(A))。則有動态規劃方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。
貪心+二分查找：（O(nlogn)）
開辟一個棧，每次取棧頂元素s和讀到的元素a做比較，如果a>s， 則加入棧；如果a<s，則二分查找棧中的比a大的第1個數，并替換。 最後序列長度為棧的長度。
這也是很好了解的，對x和y，如果x<y且E[y]<E[x],用E[x]替換 E[y],此時的最長序列長度沒有改變但序列Q的''潛力''增大。
舉例：原序列為1，5，8，3，6，7
棧為1，5，8，此時讀到3，則用3替換5，得到棧中元素為1，3，8， 再讀6，用6替換8，得到1，3，6，再讀7，得到最終棧為1，3，6，7 ，最長遞增子序列為長度4。