题目链接：https://vjudge.net/contest/216347#problem/C

 
Alice gets two sequences A and B. A easy problem comes. How many pair of sequence A\’ and sequence B\’ are same. For example, {1,2} and {1,2} are same. {1,2,4} and {1,4,2} are not same. A\’ is a subsequence of A. B\’ is a subsequence of B. The subsequnce can be not continuous. For example, {1,1,2} has 7 subsequences {1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}. The answer can be very large. Output the answer mod 1000000007.

InputThe input contains multiple test cases.

For each test case, the first line cantains two integers N,M(1≤N,M≤1000)N,M(1≤N,M≤1000). The next line contains N integers. The next line followed M integers. All integers are between 1 and 1000.OutputFor each test case, output the answer mod 1000000007.Sample Input

3 2
1 2 3
2 1
3 2
1 2 3
1 2

Sample Output

2
3
 题目大意：给你两个数组，要你求出这两个数组有多少个公共子串
个人思路：说是简单dp，但是要是想不出来就很不简单了，不说废话了，这题要求出状态转移方程，方法是用面积来求
如图，当a[i]!=b[j]时，dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1],因为多加了一个dp[i-1][j-1]的面积
当a[i]==b[j]时，a[i]等于b[j]本身构成一个相等子串，dp[i-1][j-1]加上a[i],b[i]也构成新的子串，所以在不想等的情况下加上这两个条件
dp[i][j]=dp[i-1][j]+dp[i][j-1]+1
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
typedef long long ll;
using namespace std;
const ll INF=1e9+7;
//#define INF 1e9+7
ll dp[1100][1100];
int main()
{
    ll n,m;
    ll a[1100],b[1100];

    while(scanf("%I64d%I64d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d",&a[i]);
        }
        for(int i=1;i<=m;i++)
            scanf("%I64d",&b[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i]!=b[j])
                {
                    dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+INF)%INF;//注意括号里面可能是负数，不加上会wa
                }
                else
                {
                    dp[i][j]=(dp[i][j-1]+dp[i-1][j]+1)%INF;
                }
            }
        }
        printf("%I64d\n",dp[n][m]);
    }
    return 0;
}

　　

题目链接：https://vjudge.net/contest/231313#problem/E

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

Sample Output

0.649
题目大意：输入t,代表t组测试样例，输入n,代表有n 个设备，接下来n行，每行有一个num,代表有num个厂家，接着有num对数，分别代表b,p。每个设备选择一个厂家，最后求出b与sum的最大比值
，b是你选择的厂家里最小的b,sum是你选择的p的总和。
个人思路：最先想到dfs,直接暴力搜索，没想到数据这么小也超时了,然后猜想只能用dp来写了，因为不能剪枝，感觉自己对dp还是不熟，感觉要写出来了却还是差一点，最后搜了题解，看懂了
ac代码如下
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
typedef long long ll;
using namespace std;
const ll mod=1e9+7;
#define INF 0x3f3f3f
int dp[110][20000];//dp[i][j]代表从第1~i个厂家使得带宽为j的最小价格总和，因为题目没有说带宽的范围，我们假设最大20000
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        double ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=2000;j++)
                dp[i][j]=INF;//先把每一个都初始化为无穷大
        }
        for(int i=1;i<=n;i++)
        {
            int num;
            scanf("%d",&num);
            for(int j=1;j<=num;j++)
            {
                int p,q;
                scanf("%d%d",&p,&q);
                if(i==1)//如果i=1的话，直接赋初值，因为没有上一个状态转移给i
                    dp[i][p]=min(dp[i][p],q);//注意为啥要min(),因为可能dp[i][p]会有多次到达，所以取最小
                else
                for(int k=0;k<=2000;k++)
                {
                    if(dp[i-1][k]!=INF)
                    {
                        if(k<=p)
                        {
                            dp[i][k]=min(dp[i][k],dp[i-1][k]+q);//刚开始没有想到这里为什么也要min(),以为
                            //不要也行，提交wa了，后来看代码，因为上面有个for(j)的循环，同样dp[i][k]会有多次
                        }
                        else
                        {
                            dp[i][p]=min(dp[i][p],dp[i-1][k]+q);
                        }
                    }
                }
            }
        }
        for(int i=0;i<=2000;i++)
        {
            if(dp[n][i]!=INF)
            {
                if(1.0*i/dp[n][i]>ans)
                    ans=1.0*i/dp[n][i];
            }
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

　　

 

版权声明：本文为caijiaming原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/caijiaming/p/9294403.html