前言:
这章的三道题目中有两道是可以用做的,另外一道要用到一些数论。(或者大打表?)
的第一章算是刷完了。这一张总体来说不算太难,主要都是一些简单的模拟,贪心或者和一些最基础的数论。算是巩固了一下吧。
USACO:http://train.usaco.org
USACO1.6.2.Number Triangles
思路:
太经典啦这道题。
相信初学DP的都做过吧。。。
当然深搜也是可以过的。
设表示搜到第行第列的最大和,由于只能从左上或上方转移,所以就有:
(一开始储存的是第行第列的数字)
答案就是。
代码:
#include <cstdio>
#include <algorithm>
#define N 1010
using namespace std;
int f[N][N],n,ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
{
scanf("%d",&f[i][j]);
f[i][j]+=max(f[i-1][j-1],f[i-1][j]);
}
for (int i=1;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
USACO1.6.3.Prime Palindromes
USACO1.6.4.Superprime Rib
思路:
由于质数末尾不能是除以外的偶数,所以每个位置只要枚举是中的哪一个就可以了。
对于每一位,筛一次质数即可。
代码:
/*
ID:ssl_zyc2
TASK:sprime
LANG:C++
*/
#include <cstdio>
#include <cmath>
using namespace std;
const int f[]={0,1,2,3,5,7,9};
int n,a[11];
bool prime(int m) //筛质数
{
int t=0;
for (int i=1;i<=m;i++) t=t*10+a[i];
if (t==1) return 0;
for (int i=2;i<=sqrt(t);i++)
if (!(t%i)) return 0;
return 1;
}
void dfs(int x)
{
if (x>n)
{
for (int i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return;
}
for (int i=1;i<=6;i++)
{
a[x]=f[i];
if (prime(x)) dfs(x+1);
a[x]=0;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}