小睿睿的数列

题目描述：小睿睿给了你一个长度为n的数列，他想问你该数列中满足条件（区间内存在某个数是区间内所有数的公因数）的最长区间有多少个。
题解：这道题可以看成一个非常简单的分组0-1背包问题，即每组物品只能使用一种，感兴趣对于分组背包的可以去博客园或者CSDN上搜背包九讲
#include<bits/stdc++.h>
using namespace std;
int dp[150];//在i分钟最多能拿多少分
int p[150];
int a[155];
int q[150];
int b[150];
int main()
{

int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
    scanf("%d%d%d%d",&p[i],&a[i],&q[i],&b[i]);
}
for(int i=1;i<=n;i++)//枚举有多少种，可以看成分组背包中的多少组
{
    for(int j=120;j>=0;j--)//枚举背包容量大小
    {
        //正常这一维是应该枚举这一个组中每个物品的，因为少所以就直接暴力了
        if(j>=p[i])//确保能装进去
        {
            dp[j]=max(dp[j],dp[j-p[i]]+a[i]);
        }
        if(j>=q[i])
        {

            dp[j]=max(dp[j],dp[j-q[i]]+b[i]);
        }

    }
}
printf("%d\n",dp[120]);
return 0;

}