UPC第三次随堂检测

 第七题不适合用dp,可以采用深度优先搜索，枚举全部和为x的组合，而非排列，能大大减少时间，不会超时。

每凑成一次x,提取出全部元素，标记次数加1，一个数必须使用，当且仅当它和x出现的次数是相同的。

#include 
#include 
#include 
#include 
#include 
#include 

#include 

using namespace std;

int cnt[10000+10], temp[10000+10],timecnt=0,n, x, a[1000], book[1000];

void dfs(int step,int nowsum)
{
    if(nowsum>x)
    {
        return ;
    }

    if(step>n)
    {
        return ;
    }

    if(nowsum==x)
    {

        timecnt++;

        for(int i=1; i>n;

    cin>>x;


    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }


    sort(a+1,a+1+n);

    dfs(1,0);


    int ans=0;

    for(int i=1; i<=n; i++)
    {
        if(cnt[a[i]]==timecnt)
        {
            ans++;
        }
    }

    if(ans==0)
    {
        cout<<0< 
第八题是二维费用01背包，两维度均需倒序枚举，能使数量增加就放入。

注意体力不能为0，也就是这一维容量只能是M-1，最后找到了dp[N][M-1]代表使用最大体力和能量球所能得到的最大数目，但要求体力最小，我们可以遍历整个dp数组，找到和dp[N][M-1]一样数量的结果，取消耗血量的最小值，用M减去，就是剩下的。

但遍历i=N这一层就够了，其余情况，都不如这一种情况更优。

 
 
#include
#include 
const int maxn=1010;
int N,M,K;
int n[maxn],m[maxn];  //储存消耗精灵球数量ni 和 体力值mi
int dp[maxn][maxn];   //动态规划数组

int main()
{
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1; i<=K; i++)
    {
        scanf("%d%d",&n[i],&m[i]);
    }


    for(int i=1; i<=K; i++)
    {
        for(int j=N; j>=n[i]; j--)
        {
            for(int k=M-1; k>=m[i]; k--)
            {

                    if(dp[j-n[i]][k-m[i]]+1>dp[j][k])
                    {

                        dp[j][k]=dp[j-n[i]][k-m[i]]+1;
                    }
            }
        }
    }




    int temp=M;

    for(int i=0; i<=M-1; i++)
    {
        if(dp[N][M]==dp[N][i])
        {
            temp-=i;
            break;
        }
    }
    printf("%d %d\n",dp[N][M-1],temp);
    return 0;
}
 
第九题
 
#include
#include 
# include
# include

int dp1[100010],dp2[100010];
int a[100010];
using namespace std;
int main()
{



   int t;
   cin>>t;

   while(t--)
   {
       int n;
       cin>>n;

       //dp1代表前i填卖出时获得的最大利润，本次可以卖也可以不卖
       int min1=99999999;

       memset(dp1,0,sizeof(dp1));

       memset(dp2,0,sizeof(dp2));

       for(int i=1;i<=n;i++)
       {
           cin>>a[i];

           min1=min(min1,a[i]);

           dp1[i]=max(dp1[i-1],a[i]-min1);




       }
       //dp2代表i开始后几天买入的最大利润，
       int max1=-99999999;
       for(int i=n;i>=1;i--)
       {
           max1=max(max1,a[i]);

           dp2[i]=max(dp2[i+1],max1-a[i]);


       }

       int ans=-9999999999;

       for(int i=1;i<=n;i++)
       {
           ans=max(ans,dp1[i]+dp2[i]);

       }

       cout<
 
第十题，每一个位置往前推，当且仅当推移位置之间是回文时才能状态转移
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


char ch[2000];
int len;
int f[2000];

bool check(int s, int e)
{

    bool flag = true;
    for (int i = s; i < s + (e - s + 1) / 2; i++)
    {
        if (ch[i] != ch[e - (i - s)])
        {
            flag = false;
            break;
        }
    }
    return flag;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        cin >> ch;
        len = strlen(ch);
        for (int i = 1; i < len; i++)
            f[i] = i;


        for (int i = 1; i < len; i++)
            for(int j=0; j<=i; j++)
            {
                if (check(j, i) && j == 0)
                {
                    f[i] = 0;
                    break;
                }
                if (check(j, i))
                    f[i] = min(f[i], f[j - 1] + 1);
            }
        cout<
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/563375.html