最近两天都没有更新博客力（
其实是去学了些算法，算是对计算机科学有了全新的认识吧（我之前在课本学的是什么勾八玩意儿）
CP1055 有多少个数的和是素数（经典的回溯算法，暴力枚举）
俺的做法：#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include<math.h>
void subArray(int A[], int k,int l, int n);
int y=0;
int c[1000000];//存放子集和的数组
int priArray[1000000];//存放组合的数组
void addArray(int n);
int judge(int o);
int main()
{
int i;
int n;
int m=0;
int count=0,flag=0;
int array[100000];
while(1)//录入数据
{
scanf("%d",&n);
if(n==-1)
{
break;
}
array[m]=n;
m++;
}
for (i = 0; i < m; i++)
{
for (int i = 0; i<= m-1 ; i++)//每一次都要初始化，回溯为零
{
priArray[i] = 0;
}
priArray[0] = array[i];//存储首结点
addArray(1);//直接go
subArray(array, i+1, 2, m);//接着到下一位
}
for(int q=0; q<y; q++)
{
flag=judge(c[q]);
if(flag==1)
{
count++;
}
}
for(int q=0; q<y; q++)
{
if(c[q]==1)
{
count--;
}
}
printf("%d\n",count);
return 0;
}
void subArray(int A[], int k, int l, int n)//l是最初的子集个数，n是最大长度与数组长度
{
int i;
if (k==n-1)//递归终止条件
{
priArray[l-1] = A[k];//类似于输出全排列情况
addArray(l);
}
else
{
for ( i= k; i <= n-1; i++)
{
priArray[l-1] = A[i];//分别组合
addArray(l);//输出
subArray(A,i+1, l+1,n);//再次递归
}
}
}
void addArray(int n)
{
int i;
int sum=0;
for (i = 0; i < n; i++)
{
sum+=priArray[i];
}
c[y]=sum;
y++;
}
int judge(int o)
{
for(int j=2; j<o-1; j++)
{
if(o%j==0)
{
return -1;
}
}
return 1;
}
咋说捏，这个算法毕竟有递归，还是数组得开大一点好防止溢出，同时最好画个图之类的，不然很容易把自己绕进去。
ACM2021_32 考试很经典的背包问题：
#include <stdio.h> #include <string.h> #define max(x,y) (x>y)?x:y int main () { int T,M,a,b; scanf("%d %d",&T,&M); int i,j; int dp[M+1][T+1]; memset(dp,0,sizeof(dp)); for(i=1;i<=M;i++) { scanf("%d %d",&a,&b); for(j=1;j<=T;j++) { if(j>=a) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b); else dp[i][j]=dp[i-1][j]; } } printf("%d",dp[M][T]); return 0; }
这个要用到二维数组，一个代表数量，一个代表空间，当遇到固定容量求最大价值时可以用这个，还有个贪心算法改天也要尝试一下，同理一些题目转换一下也是OK用的